• Paper Review: Safe, Flexible Aliasing with Deferred Borrows

    I’m trying something new today. I try to periodically read papers and such to stay on top of the latest research on things I’m interested in. Unfortunately, it’s easy to read a paper and have it not really stick. To combat that, today I’m trying a paper review. We did this in some of my classes in grad school, where we’d have an assigned reading for each class period and before that we were supposed to write a couple paragraphs summarizing the paper, evaluating it, and asking a few questions. So, in what will hopefully become a regular feature of my blog, today I’m kicking off my first paper review.

    Today I’m reviewing Safe, Flexible Aliasing with Deferred Borrows by Chris Fallin. This was published in ECOOP 2020. I found out about this paper from Yosh Wuyts who mentioned that it might be a good theoretical foundation for adding defer expressions to Rust.

  • How Async Functions in Traits could Work in Rustc

    One of the major goals for the Rust Async Working Group is to allow async fn everywhere fn is allowed, especially in traits. In this post, I’d like to distill some of the proposed designs and show how async functions in traits could be implemented. We’ll look at one possible way this could work, although I’d like to emphasize that this is not the only way, and many details of the design that we’ll ultimately adopt are still being worked out.

  • Perspectives on Async Cancellation

    Lately there has been a lot of discussion about async cancellation in Rust. One thing I’ve noticed in these discussions is that cancellation often means different things to people. As a result, what is a concern for one person may not be a concern for another and it may not even be possible for one person to articulate the other’s concern. I think perhaps the reason for this is that async cancellation has to be discussed from a certain perspective, and this perspective is often implied but not explicitly stated or shared. When looking from different perspectives, async cancellation can have different meanings, capabilities, and implications.

    In this post, I’d like to make an attempt at cataloging and categorizing the various perspectives we might use when discussing async cancellation. I don’t expect this to be the last word, but I hope it will be useful in clarifying the issues surrounding cancellation and serve as a starting point for more precise classifications.

  • Coming Soon: Primitive Computing

    I am excited to announce a new project I’m going to be starting to be starting this weekend!

    Have you ever wondered what it would be like to build you’re computer’s entire software stack from scratch? If so, I encourage you to check out the new series I’m going to be starting called Primitive Computing.

    Primitive Computing is going to be a live-coding project where we start with just an assembler and try to boostrap an entire computer operating system. We’ll start by getting the machine to boot, then have some fun with small boot sector programs. The goal from there will be to bootstrap a self-hosted operating environment. This will necessarily require keeping things small. Since assembly language is tedious, we’ll design and implement a slightly higher level language pretty early on. Using this, we’ll build richer operating system constructs and some simple applications such as a text editor.

    The stream will go live at 8:00 PM PST on Sunday, January 17th. The stream will be available here, or you can watch the embedded video below.

  • Streaming My 3D Printer to Google Home

    Yikes! It’s my first post in over a year!

    During the holidays I was fortunate to be able to take some time off work and was able to tackle a few projects I’ve had on the back burner for a while. One of those is being able to stream my 3D printer camera to Google Home Hub (I guess it’s technically a Google Nest Hub now). For a long time I’ve had an Octoprint instance with a camera so I can keep track of long prints without sitting right by the printer. That works well, but it’s not always the most convenient. We have a Nest Hub in the home which is great for at-a-glance information, and I thought this would be a great way to keep track of my prints.

  • ​​Automatic Website Deployment With Docker and Google Cloud Build

    Lately, I have been experimenting with serving static web sites via Docker images with NGINX. For the simple sites I am playing with, this configuration is probably overkill, but it’s not too hard to set up and it does have some advantages:

    • This approach makes it easy to capture all of your configuration information in source control, so it’s easy to spin up a new, identical instance of your site.
    • Container hosting is widely available and cheap or even free, meaning you can easily switch providers should the need arise.
    • If your site grows beyond a simple static web page, you have more room to grow because you already control your own servers.
    • Hosting providers have automated tooling that make building and deploying updates to your site as easy as pushing to a git repository.

    I have set up that last bullet point using Google Cloud Build and then hosting my site on a free f1-micro VM. So let’s see how to do it.

  • When Slow Algorithms Are Faster

    Below are timing results for two searches. One is a linear search, and one is a binary search, but I’ve hidden which search is which.

    Search Execution Time
    ??? 14 ns
    ??? 21 ns

    So which one is which? If you’ve read the title of this post, you might think this is a trick question. Let’s pretend I’m being straight with you though. In our algorithms class, we learned that linear search is O(n), while binary search is O(log n). Since log n is lower than n, obviously the lower number in the table is from the binary search. Right?

    Wrong! In this case, the linear search is actually faster.

  • Trying Out Octolapse

    About a year ago I bought a Prusa i3 MK2S 3D printer. It’s been a lot of fun, and surprisingly useful for quickly creating custom household gadgets. I primarily drive the printer using OctoPrint, and a few days ago I upgraded to version 1.3.8. One of the new improvements is that it supports the Octolapse plugin for making very nice timelapse videos. I was pretty happy with how my first attempt came out, so I thought I’d share here.

  • Fun with Side Channels

    In my undergraduate programming languages class, our professor used an auto grader and let us use it to test our programs before we turned them in. We could upload our assignment to the auto grader, where it would run our program through a number of tests and tell us our many out of the total passed. Importantly, the auto grader did not tell us what the test cases were.

    Our professor offered extra credit to any of us who could extract the test cases from the auto grader. The course had been running for years, and each time a student successfully did this they closed that particular hole. By the time I took the class, the auto grader was pretty robust. No one in my class got the extra credit.

    At the time, most of us thought of approaches like directly hacking the grading server, or trying to make our programs write the test cases out so some other place on the server. The auto grader ran on a shared server, and we could access some files stored on that server. It turns out, these approaches are pretty easy to protect against. Presumably you already have an interest in keeping your server secured, so let’s assume directly hacking it is out. Preventing your program from writing rogue files all over the system is easy enough too. Just make sure your programming environment doesn’t have any access to the outside world.

    It turns out there’s a more subtle approach: side channels. Side channels, generally, are a way of using something you control to send a message with information your aren’t supposed to be able to reveal. One common side channel is time. Let’s say you were trying to guess someone’s 4 digit PIN and you had a system that let you try as many times as you wanted. Furthermore, let’s assume that it the password checker were really slow. It would check your PIN digit by digit and each digit takes one second to check. Let’s say you try 4567 and after two seconds the system says your PIN was incorrect. You now know the first two digits are 4 and 5. So next try 4577. This time it still takes two seconds. So try 4587. This time it takes three seconds! This means we’ve figured out the first three digits. With at most 9 more tries, you’ll have figured out the password.

    There’s a reason login systems aren’t designed like that.

  • How to Convert Recursion to Iteration

    Recursion often yields concise, elegant solutions. Unfortunately, most widely used languages limit how large your program stack can grow. So what do you do if you have a recursive algorithm but need to be able to run it without growing your stack? In this post, we’ll see a generic way to take any recursive algorithm and convert it into an iterative one.