RC05: The perils and pleasures of implementing TCP from scratch

One of my main goals for my time at Recurse is to learn Rust. Since I have already implemented a DNS resolver in Rust, I thought it might be fun to dive into the next layer. And so TCP, being a more complex protocol than UDP, seemed a natural next step to explore. I’ve found learning a language through a concrete project much more fun (for me), and it forces me to use a large chunk of the language features together. I was also lucky in that TCP as a problem space seemed fit for Rust’s focus on systems programming.

I’ve previously read The Rust Book, but even after reading all of the chapters and coding out the exercises, I found that I didn’t quite grasp a sizeable chunk of Rust’s concepts and features, such as ownership and traits. Or rather I would understand it at the point of reading, but then if a week later I was asked to explain ownership, all I’d know is that Rust has this concept of ownerships… This still weak understanding of Rust’s more unique features partly motivated my writing of a toy DNS resolver in Rust. Although that did help improve my Rust afterwards, I still felt like I was using Rust as a tourist and not in any idiomatic sense.

If you’re wondering why (I chose) Rust? The hype. I’ve heard good things about it from many different places. And, it’s a systems programming language that’s strongly typed. A language that would seem to let me explore OS internals without losing my sanity to simple bugs. Additionally, I’ve also heard a lot of good things about Rust’s community, which made me feel excited and comfortable dedicating time into learning it.

Quick aside: how TCP works

The Transmission Control Protocol is a transport layer protocol that guarantees a reliable and in-order transfer of data over the network. For example, this webpage is delivered over HTTPS, which runs on top of TCP.

Scoping out a small enough TCP

TCP can be a complex protocol. It was, according to Wikipedia, introduced in 1974. As the adoption and use of the Internet has changed dramatically since then, the protocol has evolved over time. The sheer number of IETF RFCs published to describe, update, and improve TCP and its various additional features reflects this change. The Wikipedia article for TCP lists about 30 RFCs in its bibliography.¹ A few are for IP (as in IP addresses), but mostly they’re for TCP.

Since I wanted to keep my project small to start with, my main aim was to implement a “good enough”—simple and skeletal—TCP client that’ll allow me to retrieve web pages over the internet. And skipping features like congestion control and window scaling that weren’t essential to this goal. To that end, I used RFC793—the 1981 document that was the standard until its obsoletion last year—as the reference for my implementation.²

Looking at Rust’s std::net for inspiration

I was new to Rust and its patterns, and so I first based off the interface of my TCP implementation on Rust’s TcpStream with a limited subset of functions. The goal was to be able swap out the standard library’s implementation with my own implementation of TcpStream and produce the same results when calling HTTP GET on a webpage.

use std::{
    io::{Read, Write},
    net::TcpStream,
    str,
};

fn main() -> std::io::Result<()> {
    let mut stream = TcpStream::connect("example.com:80")?;

    println!("* Connected to {}", stream.peer_addr().unwrap());

    let mut response = [0; 2048];

    let _ = stream.write(b"GET / HTTP/1.1\r\nHost: example.com\r\nConnection: close\r\n\r\n");
    let _ = stream.read(&mut response);

    if let [headers, content] = &(str::from_utf8(&response)
        .unwrap()
        .split("\r\n\r\n")
        .take(2)
        .collect::<Vec<&str>>())[..]
    {
        for h in headers.split("\r\n") {
            println!("< {}", h);
        }
        println!("<");
        println!("{} ", content);
    }

    Ok(())
}

A HTTP GET request using Rust's std::net::TcpStream.

But before I could get started on replacing std::net’s TcpStream, I had to figure out how to connect my implementation to the internet. How would I be able to send and receive packets with other servers from the Rust program?

An unexpected trap? (no pun intended)

I didn’t expect it at the beginning, but one of the main difficulties with this project hasn’t so much been understanding and implementing TCP. That does take some time and is not easy to do, but more difficult, at least for me, was trying to figure out how to integrate this custom TCP/IP stack that I have with the OS’ network stack to access the internet.

One of the first rabbit holes that I went into was trying to use raw sockets to send and receive my TCP packets. Unbeknownst to me then, this proved to be quite a fool’s errand, at least on macOS because BSD sockets doesn’t allow for the reading of TCP packets. I wrote about that experience here. Chastised, I then went to peek into how another implementing TCP guide approached this initial setup. The guide used a TUN device on a Linux VM. I was still, for reasons unknown to me now (misplaced pride? naïveté?), determined to make my TCP implementation work without having to install a VM. Spoiler alert: I eventually did. I also gave away a week before that trying to figure out how to install and use a TUN device on macOS.

After deciding to use a VM and get unstuck, I next had to figure out how to use the TUN device. I wanted to understand what the associated system calls that I saw in the examples were doing, especially ioctl. And I encountered rather cryptic errors for ioctl with the raw pointers that I passed in, which I suspect had to do with Rust’s memory representation of its byte slices. In any case, although I wanted to better understand how this system call worked, it’s not a system call that’s known to be easily understood, and after a few days hitting diminishing returns, I decided that I should really move on to actually looking at TCP instead of trying to read Linux kernel source code.

Once I figured out how to successfully send a SYN packet and read the expected SYN ACK response through a TUN device using my Rust program, I was midway through my 12 week batch. I had thought that I’d be finished with the project by now (famous last words), but at least I could now start focusing on understanding and implementing TCP proper.

Translating RFC793 into Rust code

It turns out that reading the IETF RFCs wasn’t as scary as I expected. For me they were illuminating reads and great references for the moments when I was unsure of how to proceed with my implementation. I suppose this might be obvious in retrospect, considering its purpose. RFC793 gave detailed explanations on how to manage the TCP window, the different cases in which a connection could be established or closed, which made translating the spec into code less ambiguous than I expected. There was still the question of how I wanted do it in Rust, for example how would I structure the code and which traits might I want to consider using. For the most parts, I found that I could at least code out a basic working implementation.

When in doubt, code³

I used to be rather particular with commits. A (probably) irrational habit. I would get stuck trying to seek a perfect implementation on the first cut, but over time I let myself be more open to making imperfect commits, or more specifically, commits that reflected an imperfect state, as long as the code compiled. I wanted my development to follow a logical linear narrative, but when writing a program—especially for the first time—it often follows a haphazard sketch. In any case, letting myself just figure out how to get something done, coding it out, and saving those changes as checkpoints were much more important than maintaining a “clean” commit log.

Make an intentionally bad or joke version of what you want to do! Like an anti-prototype. A minimum unviable version. It will probably be fun, you’ll be defining what you do want to do more clearly, and fixing something is often more motivating than a blank screen.

Sage advice from another Recurser.

Some other fun things I learnt

• tcpdump and strace were invaluable for me when debugging my code. The former allowed me to understand what packets were being sent and received, and the latter to check the arguments passed into system calls. There was one instance where I passed in the wrong slice of bytes when calculating the TCP checksum and I learnt to use strace’s -e write=3 to print out the hexdump of the data passed to write. Learning about this (probably) saved me hours of debugging.
• While trying to read and check TCP packets in a loop, I encountered a mutable borrow error that I didn’t quite understand and learnt about Polonius. It was an unexpected limitation in Rust’s borrow checker which made for a fun learning experience and helped reinforce my understanding of the rules around mutable borrows.
• During my batch, I also worked on the cryptopals challenges in Rust and participated in the Rust for Rustaceans book club. Both were unplanned before I joined the batch, but they turned out to be very synergistic with this project. Using Rust for a similar, but different problem domain helped strengthen my understanding of Rust. Meanwhile, reading Rust for Rustaceans provided inspiration on what features of Rust might be useful. For example, I learnt about the typestate pattern in Rust from it and this turned out to be perfect for my TCP implementation.

What I might have done differently

Use a VM from the start

I’d be more open to using a VM from the beginning because it would encourage me to be less afraid of breaking things. This was the main reason why I eventually went ahead to install a VM once I realised that I didn’t want to risk breaking my computer’s network stack without knowing how to fix it. And there was also much more documented references on how to work with TUN devices in Linux than BSD or macOS, which reduced the chances of encountering unexpected and hard to debug differences in API behaviour.

Don’t be afraid to refer to existing tutorials as needed

I didn’t want to just read a guide on how to implement TCP because I wanted to work at the edge of my abilities, and give myself the opportunity to scope problems, encounter dead ends, and figure things out along the way. It helped that I was able to dedicate an extended period of time for this in a helpful community. In retrospect, I think that this was a good but perhaps misguided idea. In the end, I did consult a number of different implementations (toy and production-grade ones) and tutorials. They offered a rich example of different approaches and considerations to the problem. They also offered concrete examples of how a scoped down or real world TCP implementation could be done. Additionally, reading them introduced me to RFCs that I didn’t know about, which enriched my knowledge of the protocol. I also used selected tutorial examples as references when working with the ioctl, read, and write system calls since those APIs deal with bytes and have error messages that can be particularly difficult to debug.

What’s next

TCP as a problem space has turned out to be a surprisingly fun and fruitful domain to experiment and try out the different Rust concepts that I’ve been learning about. In implementing TCP, I had a chance to use a myriad of Rust features and also learn about network programming at the same time. Additionally, working on this within the Recurse community has been an invaluable and fun experience. It’s less demotivating to know that you’re not alone and can ask for help or pair when I’m seriously stuck.

Now that I’ve come to the end of my Recurse batch, I’m going to take a break from working on this. In my free time, I plan to next explore integrating async to handle multiple connection and also explore how security and privacy gets implemented for TCP, which seems like it’d be a nice tie-in to the cryptopals and cryptography stuff I’ve been working on.

Thanks for making it this far! If you’re interested in checking out the code, it’s on GitHub. Also if you’ve any questions, thoughts or comments, I’d love to hear from you.