Readings

This blog post imagines a programming language with “colored functions” – function are either blue or red, and differently-colored functions cannot be passed to or called from each other, plus have different calling conventions – as an analogy for async functions. The point, I suppose, is to show the unwieldiness of interactions between async and code. After trying to navigate [futures in Rust for a while](), I can see the point. As the author notes, futures don’t do much to solve the ugliness of the hand-off between sync and async code. There needs to ultimately be a method for handling separate independent callstacks.

One area where this manifests: API design. The API creator must decide whether to expose async functions, leaving sync users to de-async the result themselves, or sync functions, which async users are left to wrap (potentially wasteful, as the library had to do this itself at some point).

The HN comments for this post are insightful, with the top commenter noting that the red-blue language is “essentially Haskell” (with blue and red monoids), and another noting that golang solves this problem by making the whole program “red” (async).

A lot of PL research is about better patterns of programming, covering new ways of abstracting patterns that you encounter in a real codebase. Two of the most beloved courses at NU, Prof. Robby Findler’s courses on Compilers and Programming Languages, are built on that principle: they are basically programming seminars, with very little formal introduction to the concepts they cover - instead letting them reveal themselves through the assignments. Indeed, a compiler isn’t built the way it is because the concept of a ‘compiler’ is written in natural law - it’s a revealed way of handling the complexity that comes with all the forms the grammar of the language can express itself.

The main transformation to enable tail calls is to replace the function call f with a goto, calling destructors on local variables, then replacing the original arguments of the current function with the arguments of f. The normal borrow semantics for the return should therefore apply.

A tail call is only valid if there is nothing to be done in the caller after the call. This implementation checks this by first creating a node for become in HIR, then later, in MIR, checks that the “basic block being branched into” either “has length zero” or “terminates with a return.” I assume that this “basic block being branched into” contains whatever follows the become statement, and branches to another basic block if there’s anything more to do after the become; otherwise falling into the cases mentioned.

Also notes the main reason tail calls haven’t been implemented yet: portability. They’re not supported in several targets, like WebAssembly, which is something that the Rust developers apparently won’t tolerate.

IPFS is a distributed file system. It combines ideas from Kademlia, Bittorrent, Git,and Self-Certified Filesystems, taking respectively 1) routing and node identity, 2) block exchange, 3) Merkle tree-based verification and versioning, and 4) self-certification - addresses derived from public keys.

The result is something like a DHT that stores Git objects and uses the Bittorrent protocol for distribution. The certificate system, which does not rely on a trusted 3rd party to map addresses to public keys, is another major feature, allowing public-key encryption and ensuring that a malicious node can’t impersonate a node that has already established trust.

The block exchange protocol, called BitSwap, is a modified version of Bittorrent’s. Bittorrent provides incentives for seeding - the standard seeding strategy is to prioritize seeding to the n peers that are themselves the best seeders. BitSwap is similar, but the choice of which peers to seed to is probabilistic, depending on that peer’s ratio of sent:received objects. Since this probability is based on lifetime ratios, a peer can stop uploading for a short time and not have its download rates affected much.

Bittorrent also encourages the sharing of rare pieces by making sure that rare pieces are requested first. If this is a demand-side incentive - demand is increased for rare pieces - BitSwap’s solution is supply-side - peers are encouraged to seek objects that their peers also want. This allows a peer to contribute even if it currently does not want any objects.

The file system itself is implemented as a Merkle DAG, very similar to Git’s. Objects have links to other objects, represented as their hashes. Tree objects represent directories, blobs data, and commits represent snapshots of a collection of objects in some state. IPFS, unlike git, also has lists, which can contain blobs or other lists. Like Git, objects are deduplicated because they are addressed by their hashes. They are also immutable and permanent: once mutated, an object’s hash changes, and there is no command in the protocol to delete the previous version.

These attacks involve using DNS rebinding to allow a website to send requests to HTTP servers on a user’s machine. The targets include RPC servers included with uTorrent and with Blizzard Updater.

DNS rebinding is meant to get around the same origin policy. The scheme is: setup a domain and a DNS server with a short TTL. Once that’s expired, serve a script that makes a request to the origin domain - but when the browser makes a DNS request, respond with localhost instead. That way, the request gets routed to the target instead.

Each vulnerable app also failed to provide authentication that could prevent the attack. The Blizzard Updater included an auth token with each response, presumably setting Access-Control-Allow-Credentials to prevent bad actors from reading it - but DNS rebinding circumvented this.

Asynchronous programming usually aim to make it easier to reason about asynchronous operations. For example, by avoiding explicitly working with threads – the asynchronous library handles that itself– you can avoid complexity while avoiding the overhead of unnecessary thread spawning. In Rust, these constructs are ‘tasks.’ When you run a task, instead of blocking, it returns control to the executor thread. The task runs until it would block, then returns Async::Pending. You also provide it a Waker so that it can wake itself up again.

An executor works by running each of the tasks until they block, and then parking. A Waker contains a link back to the executor and inserts the task in the executor’s ready set before unparking it.

Futures are tasks that can be chained. They must implement a type Item that is the result of the computation, a type Error, and a poll method that returns Async::WillWake or Async::Ready(data: Item).

Futures are designed to be state machines: eg, one that alterates between the states Reading and Writing, returning Async::NotReady when it can’t proceed.

If you create a socket and call connect(dst, port) on it, or first call bind(src, port) with port 0, the kernel will allocate from the pool of up to 64k available ports. However, with with SO_REUSEPORT, you can also share ports to create an effectively unlimited number of connections - as long as the destination address is different for each connection sharing the same port. To have multiple connections to the same IP/Port pair, you can use different source IP addresses instead.

SO_REUSEADDR behaves slightly differently than SO_REUSEPORT, allowing reuse of addresses in the cooldown period after a process releases a socket, plus allowing binding of wildcard addresses (0.0.0.0) and normal addresses to the same port.

There are various implementation concerns (ie, bind is fine, but after connect one of the reuse rules is broken) that the linked post discusses.

An overview for the reasons that more recent languages (Rust, Go) have avoided the full-on object-orientedness of Java, C#, et. al. Traits and interfaces allow for polymorphism while avoiding the problems of inheritance - they’re not hierarchical, so they avoid issues like the diamond problem that result when implementing new objects that don’t fit easily into the existing hierarchy. Non-hierarchical structs also avoid the bloat of carrying around unnecessary parent fields.