Chameth.com - posts like docker-automatic-nginx-proxy, over-the-top-optimisations-in-nim, why-you-should-be-using-https but not break-everything-fuzz-testing, debugging-beyond-the-debugger

An interesting Tailscale + Docker gotcha

2026-01-29T00:00:00Z

As I’ve written about before, I use Tailscale for a lot of things. I thought I had it set up in a reasonably secure manner, but I recently noticed a problem.

I use Tailscale’s ACLs to limit what each node can access, based on the tags I apply to it. So an app node can’t access anything via Tailscale, while an integration or server node can access things tagged with either app or integration. This is expressed pretty simply in the Tailscale ACL JSON:

{
	"tagOwners": {
		// Servers that can be SSH'd into
		"tag:server": [],
		// Applications that are exposed on tailscale but never connect out
		"tag:app": [],
		// Things which talk to other services over tailscale (connecting to apps etc)
		"tag:integration": [],
	},
	"grants": [
		{
			// Users can access everything
			"src": ["autogroup:member"],
			"dst": ["*"],
			"ip":  ["*"],
		},
		{
			// Servers and integrations can access integrations and apps
			"src": ["tag:server", "tag:integration"],
			"dst": ["tag:integration", "tag:app"],
			"ip":  ["*"],
		},
	],
}

Over the past week I’ve been setting up a private Forgejo instance behind Tailscale, complete with an actions runner that runs things using a docker-in-docker container. I didn’t want the runner knowing anything about Tailscale, so I had it configured to speak to Forgejo direct over HTTP (forgejo:3000) instead of using full Tailscale HTTPS URL that I use when accessing it (http://git.example-net.ts.net/)¹.

Everything was going fine, until I forgot to do that translation… and it worked. My Forgejo action runners could access anything on my tailnet. I run several things on Tailscale that just have authentication turned off, on the basis that only authorised devices can access them. Things like the admin interface for this website. I definitely didn’t intend for any workflow I run on my git server to have access to edit my website!

This wasn’t just limited to Forgejo, either. Any docker container I was running could access the tailnet. In hindsight it’s fairly obvious why: the host is running Tailscale, connected as a node tagged with my server tag. That creates a tailscale0 interface, and automagically sets up iptables rules to route Tailscale traffic over the interface. Docker also automagically sets up iptables rules to bridge traffic, and apparently these two sets of rules interact in such a way that traffic from Docker containers is allowed to route via the tailscale0 interface.

I say it’s fairly obvious in hindsight — there’s no reason why Docker would special case any particular host interface after all — but it still feels pretty surprising. Because both bits of software inject their own iptables rules, I never really had a good mental model for how they interact. The host Tailscale node was a completely separate building block to Docker. It would be a pain to use either of them if they didn’t do these rules, but it’s also one of the reasons I don’t really like “magical” things².

There are lots of ways to fix this, but none of them feel particularly great. You can configure both Tailscale and Docker to not automatically fiddle with iptables and handle the rules yourself, but I really hate dealing with iptables³. As a stopgap I did hold my nose and add some iptables rules to drop traffic to the tailscale0 interface if it originated from the IP ranges that Docker was configured to use:

iptables -I DOCKER-USER -s 192.168.0.0/16 -o tailscale0 -j DROP
iptables -I DOCKER-USER -s 172.17.0.0/12 -o tailscale0 -j DROP

The DOCKER-USER chain is a nice little escape hatch; it comes before the main auto-generated DOCKER chain, and Docker leaves the rules in it alone.

So I added these rules, and felt pretty good about myself, and then… everything started breaking in weird ways. After some debugging I realised the problem was DNS⁴. The server’s DNS resolver is 100.100.100.100, a special Tailscale address. This is so that it can resolve tailnet hostnames via MagicDNS (and so I don’t have to configure my custom DNS servers manually on each device; Tailscale does it for me). My new iptables rules inadvertently dropped all the DNS packets coming from docker containers. D’oh.

Obviously the solution here is to double down and add MORE iptables rules:

iptables -I DOCKER-USER -s 192.168.0.0/16 -d 100.100.100.100 -o tailscale0 -j ACCEPT
iptables -I DOCKER-USER -s 172.17.0.0/12 -d 100.100.100.100 -o tailscale0 -j ACCEPT

This got DNS working again, but it all feels a bit gross. Not least because to actually make these persist you need to use iptables-save, and then you also get all the rules that both Docker and Tailscale have inserted. I came across a script to filter out the Docker ones, but… yuck⁵.

I realised a cleaner idea might just be to lock down what server tagged nodes could access within Tailscale itself. That way I can avoid touching iptables at all. It’s handy to be able to curl services from the host when debugging, but it’s not really necessary. So I removed that access, and… stuff broke again. I’m using my Forgejo instance as a registry for some of the docker images I run, so the docker daemon needs to be able to reach it. I ended up making a new tag for infrastructure, which can be accessed from server devices. This does still allow all the docker containers to reach Forgejo, but I already have it set up with appropriate access controls and public/private repository splits. Forgejo is a service designed to run publicly, so this seems a reasonable trade-off for convenience. I used the tests feature of Tailscale’s ACL config to make sure I’d got the rules right:

{
	"tests": [
		{
			// Servers can only access infrastructure
			"src":   "tag:server",
			"proto": "tcp",
			"allow": [
				"tag:infrastructure:8080",
			],
			"deny": [
				"100.84.16.43:8080",
				"me@example.com:8080",
				"tag:server:8080",
				"tag:app:8080",
				"tag:integration:8080",
			],
		},
	],
}

The whole situation still feels a bit messy. If I ever get around to switching to nftables I might loop back and manually craft some rules for routing traffic, instead of leaving Tailscale and Docker to do their own thing.

I discovered later on that logging into the container registry at forgejo:3000 actually issued a redirect to https://git.example-net.ts.net/ so this was all basically for naught… ↩︎
I didn’t use Tailscale’s MagicDNS for a long time just because the word “magic” put me off. Only when I eventually got around to learning how it worked, and seeing that it wasn’t really that magical under the hood, did I change my mind. ↩︎
nftables seems far better in lots of ways, but I can’t really be bothered migrating. Maybe next time I reimage the server for whatever reason… ↩︎
It’s always DNS… ↩︎
Again, nftables would almost certainly help here. It actually has (gasp) configuration files. But again, I really didn’t want to spend the time migrating. ↩︎

Docker reverse proxying, redux

2022-12-06T00:00:00Z

Six years ago, I described my system for configuring a reverse proxy for docker containers. It involved six containers including a key-value store and a webserver. Nothing in that system has persisted to this day. Don’t get me wrong – it worked – but there were a lot of rough edges and areas for improvement.

Microservices and their limitations

My goal was to follow the UNIX philosophy of “do one thing and do it well”. Unfortunately, that doesn’t really work when applied to network services that have to interact with one and other. UNIX tools are built upon a common file system and simple data passed over STDIN. Microservices don’t have that shared foundation. You could make one: companies that use microservices in anger often have a team that deals with the “developer experience” of creating and using microservices. But as a solo developer that’s not something I wanted to spend my time doing.

This became very apparent when trying to debug issues. In the UNIX world, if your series of commands piped together does something strange you can simply echo the data at various stages. Not so much when that data is flying around on a network, going into and out of things like etcd. Trying to figure out why a certificate hadn’t been acquired was a case of searching through logs from four containers, none of which had particularly good logging. There are many ways to get insight into what’s happening with microservices but, again, that’s not something I wanted to do myself.

Over time, and with experience in other projects, I came to realise that microservices only really make sense if you’re unable to deploy a monolith. For tech companies this naturally happens when different teams contribute to the same service: splitting it out into smaller services that are wholly owned by individual teams makes sense. For solo developers, that never happens. You can still gain the other benefits of microservices – such as code separation and having clearly defined APIs – by sticking to certain coding standards.

Proxy inconveniences

As well as being unhappy with the microservice nature of the solution, I wasn’t pleased with nginx. If you requested an unknown domain, nginx would use the first server block in its config to serve a response, instead of sending an “unrecognised name” alert as I wanted. It was a minor issue, but it irked me.

So from nginx I switched to haproxy. It has a strict-sni option when configuring TLS connections which makes it behave properly. It also performs a lot better for this type of workload than nginx. All was well for a while, but then I started getting alerts that requests were occasionally failing. I couldn’t reproduce the issue, but my nightly jobs to build and push containers managed to hit it nearly every night, causing them to fail.

After some investigation, I found that the haproxy developers had refactored the header parsing code, and neglected to properly reset flags when multiple requests were sent over the same connection. There was a patch, but it wasn’t released. No problem, I thought, I’ll just cherry-pick it onto the last release… Except that haproxy use Git in the most convoluted manner I’ve ever seen – they have one repository per release. This makes it harder to patch, but it also made me question whether I trusted them to ship stable software: there were no tests for the header parsing code (which is both fundamental and finicky, the perfect target for tests), the source code management was weird, and they didn’t seem in any rush to patch this bug.

Not long after that issue, Greg managed to encounter another bug where haproxy returned a 500 error whenever the upstream server replied with a particular, perfectly valid, header. The die was cast – it was time to move to something else.

Not Invented Here syndrome

Looking for a new solution, there were many more options than back in 2016. I’m still convinced, however, that anything exposed to the Internet should not have access to run docker containers. It’s the modern equivalent of running a CGI script as root. That single requirement eliminates most off-the-shelf solutions. What do you do when nothing quite meets your specific requirements? You make something yourself! My new solution has two components: Dotege and Centauri.

Dotege is a replacement for the microservices that monitored containers and obtained certificates. It’s fundamentally a templating engine - whenever the containers change, it evaluates a template and saves the result to disk. The template has access to details about the containers, their labels, ports, and so on. Dotege can also obtain certificates from Let’s Encrypt, and raise a signal against another process whenever the template or certificates change. I used this to generate the configuration and certificates used by haproxy for a while, and more recently changed the template so that it works for Centauri.

Centauri is my own reverse proxy. It’s configured using a simple text file and can also obtain certificates from an ACME provider. It doesn’t serve static content, has no knowledge about docker, and avoids the other bells and whistles that adorn most reverse proxies. It also has good test coverage to ensure that I don’t, say, accidentally break header parsing.

As a software engineer I enjoy writing software, but I also enjoy running simple, easy to understand software. That’s what I’ve achieved here: it’s very easy to identify where the problem is if anything goes wrong, both are small Go programs rather than vast sprawling C monstrosities, and their interaction is primarily through a file written to disk that can be inspected or edited as needed.

An introduction to containers

2020-03-01T00:00:00Z

So. Many. Containers.

I’m a huge fan of (software) containers. Most people I know fall in to one of two camps: either they also use, and are fans of, containers, or they haven’t yet really figured them out and view them as some kind of voodoo that they don’t really want or need.

I’m writing this short guide to explain a little how containers work - and how running something in a container isn’t really that much different to running it normally - to hopefully enable more people in that second group to give them a try. It’s aimed at people who have a fairly good grasp of how Linux works.

Containers are often mentioned in the same breath as VMs, which is not a helpful comparison or analogy. Think of containers as standard units of software, much like how Intermodal containers are standard units of freight transport across the world. When a company internationally ships goods in volume there isn’t a question about how they’re packaged - they go in an intermodal container. The same container can be deployed on a freight train, a lorry, or a ship. The haulage company doesn’t need to care what’s in the container because they’re completely standardised. Likewise, with software containers you don’t really need to care about what’s inside: the software you’re deploying could be written in Go, Python2, Python3, Bash, PHP, LOLCODE, or anything¹.

What does a running container look like?

When you run a container, you’re just running a process. In a lot of ways it’s not very different to what happens if you were to start the same process on the host computer.

For example I have a container that just runs cat(1). With no arguments, cat will read from stdin until it receives an EOF, so it’s handy to test with. If I run ps a on my computer, I can see the cat process in amongst everything else I’m currently running:

    PID TTY      STAT   TIME COMMAND
   7199 pts/1    Ss     0:01 /usr/bin/zsh
 323806 pts/0    Ss+    0:00 /bin/cat
 324120 pts/4    R+     0:00 ps a

The /bin/cat process is in a container, and the ps a underneath it is just running like normal on my desktop. They look very similar, right? If I look under /proc/323806 I can see all the usual attributes, the same as any other process running.

If I run ps in a container, though, it’s a different story:

    PID TTY      STAT   TIME COMMAND
      1 pts/0    Rs+    0:00 ps a

So inside the container it looks like there’s only one process running. It can’t see anything running “outside” on my desktop. The secret here is that this isn’t a special container trick: this is just a feature of the Linux kernel called namespacing.

If we go back to procfs and look at the ns/pid node we can see the process in the container is in a separate PID (process ID) namespace to the one on my desktop:

# readlink /proc/323806/ns/pid  
pid:[4026534564]
# readlink /proc/7199/ns/pid
pid:[4026531836]

Almost all² processes running ’normally’ on my desktop have the same PID namespace, whereas each container gets their own by default. PID namespaces are hierarchical: a new process is assigned a PID in its own namespace, and the parent namespace, and the grandparent namespace, and so on. That’s why I can see the process running in the container from my normal shell - the container’s namespace is a child of the main namespace all of my desktop software is running in.

Linux supports - and container software makes use of - a bunch of other namespaces too: mount points, network, UTS³, cgroups, and more. These all play a part in isolating a container from the system it is running on.

You can manually run a process with unshare(1) to “unshare” some namespaces from the parent process. For example if I run unshare -fp --mount-proc ps a, it looks very similar to running ps instead the container:

    PID TTY      STAT   TIME COMMAND
      1 pts/4    R+     0:00 ps a

So: a process running inside a container is just a heavily namespaced process running otherwise normally in the operating system. No voodoo magic here!

What about the filesystem? What are ‘images’?

Containers run in their own mount namespace meaning mount points can be different inside the container to those on the host. This means the container can have a different / mounted to the host, effectively giving it its own filesystem.

The root filesystem of the container is defined in the container’s image. If I use Docker to run a container using the Ubuntu image (docker run ubuntu), the root filesystem inside that container will resemble a minimal ubuntu install. Note that this is just the filesystem: the container doesn’t have its own kernel.

You might be thinking that sounds pretty inefficient. Downloading Ubuntu is definitely not instant, and doing it for every application you run would be insane! Quite. Containers solve this by using filesystem layers. These are stacked on top of one another to create the final filesystem. Each layer can be retrieved and cached independently of all others.

Say (for simplicity) that the Ubuntu image is a single layer. If I run one container with that image, then the layer will be downloaded and cached once. If I run three hundred containers with that image then the layer will be downloaded and cached once. Even better, if I use another image that’s based on Ubuntu but adds some software on top, only the “on top” layer will be downloaded if I already have the relevant “Ubuntu” layer cached.

If all the layers are cached, what happens when you change a file? This is dealt with using the copy-on-write technique: when you modify a file it is copied from the source layer and the changes are only made in a new layer. This is handled by the OverlayFS filesystem which is part of the mainline kernel.

When a container is running, changes made to its filesystem are temporary, and do not persist across container restarts. To persist data - or introduce new data to a container - you can mount volumes. How this works varies depending on how you’re running your container, but at the basic level it is pretty much the same as bind-mounting (mount -o bind).

You may be familiar with using chroots to change the apparent root directory of processes, perhaps with full-blown “jails” built on top. Containers offer much better isolation thanks to the use of namespaces. Instead of being constrained to a portion of the host’s filesystem, they don’t even have it mounted! Containers also get to specify their environment - if they expect in certain places, for example - instead of the sysadmin having to manually set up the chroot. Finally, containers offer much more fine-grained control over what processes can do (if you want it), and allow much more advanced use-cases such as inter-container networking.

Images and filesystems employ a little magic to ensure that layers are reusable and cacheable, but again there’s nothing terribly special about them: a container has a filesystem that appears to it to work the same way as a filesystem on the host, and it’s using a standard filesystem shipped with the kernel.

How about networking?

Again, networking is namespaced, so a container has its own network stack, its own virtual network interface, its own IP address and so on. How that network interacts with your real network depends on how you’re running the container. Docker, for example, can add iptables rules to NAT traffic between containers' networks and the outside world.

Containers can generally be connected into networks, and can communicate amongst themselves without the traffic actually leaving the host machine. This allows you to, for example, run a SQL database and connect it to a web application without ever exposing the database to the outside world. Moreover, as well as being isolated from the outside world, it’s isolated from other containers in other networks. If one of your applications has a crazy bug or is compromised, this significantly limits the damage it can do.

You have to explicitly opt in to “publishing” ports from a container, which exposes them to the outside world (either directly, or via a load balancer or some other middle-man, depending on how you’re running the container). This means you can pick and chose how the outside world sees the app you’re deploying: if it’s a web service that listens on both port 443 and port 80, you can chose to only expose the encrypted port.

If you run some containers and create some networks, you can see the interfaces and bridges on the host:

$ ip l
...
6: br-2405a8cc0445: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP mode DEFAULT group default 
    link/ether 02:42:3e:fa:23:62 brd ff:ff:ff:ff:ff:ff
8: veth8ed0735@if7: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue master br-2405a8cc0445 state UP mode DEFAULT group default 
    link/ether b2:c1:5d:55:26:9b brd ff:ff:ff:ff:ff:ff link-netnsid 2
10: veth541d84b@if9: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue master br-9d7bc4024c1a state UP mode DEFAULT group default 
    link/ether 86:aa:5f:ee:da:1a brd ff:ff:ff:ff:ff:ff link-netnsid 1

This shows a bridge and two virtual NICs, just the same as if you’d manually created them (albeit with seemingly random names). So: as before, nothing special here.

Docker? Compose? K8s? Floccinaucinihilipilification?

(OK, Floccinaucinihilipilification isn’t actually a container technology, as far as I’m aware.)

Docker is the most popular container engine - that is, the bit of software that actually runs containers. It’s responsible for setting up all those namespaces we found, downloading and caching image layers, and actually starting and stopping the processes. Docker runs as a system-wide daemon - when you run a command like docker run ubuntu it actually just instructs the daemon to do the work.

There are several alternatives to Docker for running containers; one interesting one is Podman which runs containers without a daemon. Container engines have all standardised around the same image format looked after by the Open Container Initiative, so an image you build in Docker can be used in Podman, or pretty much any other engine.

Docker compose is a tool for defining and running multiple-container applications. I mentioned earlier running a database alongside a webapp - in practice to do this you’re going to have to configure a network for them, configure a mount point for the database to persist its data on, pass credentials in to both the database and the application, and so on. Doing all that by hand is tedious and error prone.

Docker compose lets you write “compose files”, which are simple yaml descriptions of the containers you wish to run, their properties, and details about any volumes or networks you may want. Out of the box, docker-compose will create a default network for each compose file you run so the containers within it can communicate.

Kubernetes is a container orchestrator, designed to automate deployment and management of large numbers of containers. It works with Docker under the hood, but provides a huge amount of tooling on top to allow you to deploy applications and manage their dependencies. It runs across multiple physical (or virtual) machines (while still allowing containers to communicate privately), and can support massive workloads by scaling out services (running multiple copies of a container on different hosts) and load balancing. Kubernetes is sometimes shorted to k8s (as in K - 8 elided letters - s) because computer people don’t like long words.

OK, they make sense now. But why bother?

Hopefully if you’ve read this far you’ve already picked up on some of the potential benefits, but this is my personal list:

Isolation. If I run some software in a container, there is very little it can do to upset me. It’s not going to leave bits of itself all over my filesystem, it can’t steal all of the secrets in my home directory, I can even limit its CPU and memory resources if I want. If I decide to stop running it, I just delete the container and it is completely gone: no trace remains.

Ease of use. If you give me a container image I have a very good idea of how to run it already. I might need to do some minor configuration to expose ports or mount volumes, but there’s no question about how to run it, how to make it automatically start, and there’s no “installation” procedure. If I want to then swap it with an alternative (say, move from MySQL to MariaDB), it’s potentially just a case of changing the name of the image I pull.

Dependencies included. Containers just run. Python 2 software includes Python 2 and just work. Python 3 software includes Python 3 and just work. I don’t have a massive headache trying to run both at the same time, because they take care of their own messes. Similarly I’m not going to have to install npm or cargo or composer to pull in dependencies for an application: that’s going to have been done in the build process.

Reproducibility. As a fallout from having dependencies included and being isolated from everything else, containers give you amazing reproducibility. If it “works on your machine” in a container, it’ll almost certainly work in production because it’s the exact same environment.

Standardisation. At the start of this article I called containers standard units of software. One of my favourite advantages of containers is that you basically get an API to list all the software you’re running. Most container engines let you supply labels attached to containers as well, so you can add your own annotations. I use this to annotate services which expose HTTP endpoints, and I have a tool that automatically generates SSL certificates for them and configures haproxy to route traffic to them. I can’t imagine how I’d do this without containers - I imagine it’d involve a lot of manual work.

Hopefully this has helped demystify containers a little. If you feel like I’ve missed something important out, or I’ve left you more confused than when you started, feel free to drop me a note using the feedback form below.

OK, maybe you should care if you’re deploying something written in crazy languages like PHP. ↩︎
Some multi-process apps, such as web browsers, are starting to use namespaces to enhance security, as do certain package systems like Flatpak ↩︎
“Unix timesharing system”; in practice this means having a separate hostname ↩︎

Over-the-top optimisations with Nim

2018-12-09T00:00:00Z

Christmas Tree from Advent of Code 2005

For the past few years I’ve been taking part in Eric Wastl’s Advent of Code, a coding challenge that provides a 2-part problem each day from the 1st of December through to Christmas Day. The puzzles are always interesting — especially as they get progressively harder — and there’s an awesome community of folks that share their solutions in a huge variety of languages.

To up the ante somewhat, Shane and I usually have a little informal competition to see who can write the most performant code. This year, though, Shane went massively overboard and wrote an entire benchmarking suite and webapp to measure our performance, which I took as an invitation and personal challenge to try to beat him every single day.

For the past three years I’d used Python exclusively, as its vast standard library and awesome syntax lead to quick and elegant solutions. Unfortunately it stands no chance, at least on the earlier puzzles, of beating the speed of Shane’s preferred language of PHP. For a while I consoled myself with the notion that once the challenges get more complicated I’d be in with a shot, but after the third or fourth time that Shane’s solution finished before the Python interpreter even started¹ I decided I’d have to jump ship. I started using Nim.

Introducing Nim

Nim, formerly Nimrod, is a compiled language that takes a lot of cues from Python. It has a very nice and familiar syntax, a reasonable standard library, and it’s fast. I’d thought about learning it before but didn’t really have anything suitable to use it on, until now. The code I used for my day one part one answer looks like this in Nim:

import math, sequtils, strutils

echo readFile("data/01.txt").strip.splitLines.map(parseInt).sum

It’s a one liner that Python would be proud of. The difference with Nim, though, is that this compiles down to C, and from there you get all the benefits of an optimising C compiler and linker. You end up with a blazingly fast stand-alone binary.

Losing my marbles

Day 9 of this year’s Advent of Code proved interesting to optimise, and I’m going to walk through some of the steps I took and their impact. I’m in no way a Nim expert and this is for a program that will be run once and then thrown away, so please don’t take this too much to heart.

Day 9 presents a marble game played by Santa’s elves, whereby marbles with increasing values are added to a circle according to certain rules; every 23rd marble is special and the elf playing it gets to keep that one and also pick up a marble a certain number of places away. The winner is the one with the highest marble value at the end. It doesn’t sound like a particularly thrilling game, but as far as I can tell there’s no way to easily predict the winner without simulating it step-by-step so it makes for an interesting problem.

Naive solution: over 10 minutes

My puzzle input called for a game with 72,104 marbles. My initial approach was to use a sequence (similar to a list) to store the values of the marbles as they’re added to the circle. This got an answer for part 1 in a about 10 seconds and put me at number 124 on the global leaderboard for fastest completion. Unfortunately, when part 2 was revealed it asked me to calculate the result if there were 7,210,400 marbles in play.

Obviously a puzzle 100x larger would take at least 100x longer to run, and almost certainly a lot more than that. There isn’t a way to calculate the advance stages more quickly, so the only thing to be done is to make it run a lot faster. Seven million iterations isn’t really that much of a burden for a modern CPU: for the code to be running this slowly the execution time of some of the operations must be scaling with the number of marbles. A quick look through the documentation reveals:

proc del[T](x: var seq[T]; i: Natural) {...}
deletes the item at index i by putting x[high(x)] into position i.
This is an O(1) operation.

proc delete[T](x: var seq[T]; i: Natural) {...}
deletes the item at index i by moving x[i+1..] by one position.
This is an O(n) operation.

Because we have to delete a marble at an arbitrary point and maintain the ordering of the others, I was using the delete() proc which has an O(n) runtime. The other potentially costly operation is inserting a new marble; the documentation doesn’t mention the runtime but all of the nim docs have a direct link to the source code, and we can see that inserting an element requires iterating over all the elements after it, so it’s also O(n) in the worse case.

DoublyLinkedLists: ~500ms

When you need performant inserts and deletes in a list, the go-to solution is a linked list. Because nodes store references to their neighbours (instead of being stored consecutively in an array or list), delete and insert operations are O(1): you simply need to change a few pointers. Nim’s lists package provides a convenient DoublyLinkedList that I went ahead and used.

Instead of using the old insert and delete methods I now had my own which simply manipulate the nodes’ previous and next pointers:

func insertAfter(node: DoublyLinkedNode[int], value: int) =
    var newNode = newDoublyLinkedNode(value)
    newNode.next = node.next
    newNode.prev = node
    newNode.next.prev = newNode
    newNode.prev.next = newNode

 func remove(node: DoublyLinkedNode[int]) =
    node.prev.next = node.next
    node.next.prev = node.prev

This implementation brought the runtime down to a respectable 500ms, which handily beat Shane’s PHP implementation. It was still an order of magnitude longer than any of my other solutions, though, so I wasn’t happy yet.

Reduced imports: ~470ms

One thing I was conscious of from trying to make Python performant was how the number of imports can pile on to startup time. I had a couple of unused imports that were easy to shed, and I also decided to implement my own linked list in favour of nim’s lists module. All this involved was defining a type and then replacing my usages of DoublyLinkedNode[int] with my new Marble.

type
    Marble = ref object
        next, prev: Marble
        value: int

These few changes didn’t have a huge impact, but I was clutching at straws and every 30ms was a small victory.

Inlining methods and small optimisations: ~420ms

Thinking the code was about as fast as I was going to get it, I made a final pass to see if there were any little tweaks I could make. First off, I added the inline pragma to my insert and remove methods, to hint to the C compiler that they should be inlined. I was concerned that the overhead of calling a function seven million times would add up, and inlining the fairly simple operation seems reasonable. It’s entirely possible the C compiler was already doing this (they’re pretty clever), but making the hint explicit in Nim is really easy so there’s nothing to lose:

func insertAfter(node: Marble, value: int) {.inline.} =
    var newNode = new(Marble)
    newNode.value = value
    newNode.next = node.next
    newNode.prev = node
    newNode.next.prev = newNode
    newNode.prev.next = newNode

func remove(node: Marble) {.inline.} =
    node.prev.next = node.next
    node.next.prev = node.prev

I also made some small algorithmic tweaks. These are usually the bread and butter of optimisations but for this problem there were only a couple I could see:

We only care about the current player every 23rd marble, so instead of tracking the player each turn we can just calculate a 23 player jump when needed
Instead of testing whether the current marble is divisible by 23, which is potentially non-trivial for large numbers, we can use a separate variable that just counts down from 23 and gets reset
Instead of calculating the boundary condition (100 * marbles) whenever it’s used, we can put this in a variable and calculate it once up-front. (The C compiler probably handled this for us anyway)

These combination of tweaks saved another 50ms, and it seemed like there wasn’t a whole lot left that could possibly change.

Non-reference counted objects: ~180ms

While I was pondering further improvements, Shane mentioned that he managed to make PHP’s garbage collector segfault with his solution. That got me thinking: what would happen if Nim didn’t have to worry about garbage collecting our marbles? We have a fixed amount of them and don’t need to worry about memory leaks as the program runs for half a second and then quits. Changing the Marble type and manually allocating memory for it — something that is virtually impossible in languages like PHP or Python — was trivial in Nim:

type
    Marble = object
        next, prev: ptr Marble
        value: int32

proc insertAfter(node: ptr Marble, value: int) {.inline.} =
    var newNode = cast[ptr Marble](alloc0(sizeof(Marble)))

Taking the garbage collector out of the equation over doubled the performance! Still, it was my only solution that took more than 100ms and that bothered me…

No looking back: ~120ms

Thinking about memory allocations made me take a hard look at the structure of the Marble type. Each of the seven million marbles has a previous pointer that we only use to backtrack by a fixed amount every 23rd play, which seems wasteful. If we reduce the amount of memory we have to allocate, we’ll logically reduce the time taken allocating it.

As the game is simulated we keep track of the “current” marble, so why not keep track of the marble eight behind that? That would allow us to turn the doubly-linked list into a singly-linked list and save a whole bunch of memory. This ends up being slightly complicated as initially there aren’t eight marbles, and every 23rd play we jump the current position backwards (and without previous pointers, we can’t jump the “current minus eight” pointer backwards).

To work around these issues, I added a “trailing” pointer that gradually drifts backwards to eight behind the current pointer as moves are played. There are 22 normal moves that each advance the current pointer by two, so there’s plenty of time for this to happen.

var
    currentTrail = current
    currentTrailDrift = 0

# When a standard move occurs:
current.next.insertAfter(i)
current = current.next.next
if currentTrailDrift == 8:
    # Keep the trail eight marbles behind the current one
    currentTrail = currentTrail.next.next
else:
    # Don't move the trail so it drifts away by two marbles
    currentTrailDrift += 2

This is one of those optimisations that makes the code a bit harder to follow, but it sliced a third of the runtime off and takes us tantalisingly close to that 100ms threshold.

One bulk order of memory, please: ~50ms

Thinking about memory allocations, I realised we were doing seven million small allocations over the lifetime of the program. We know upfront how many marbles there are going to be and will need to allocate memory for them all at some point, so why not just do it in one big bang?

Fortunately, again, Nim lets you dive from the high-level Python-like world down to the nitty-gritty of memory management and pointers without blinking. Now after reading the puzzle input, I allocate a big chunk of memory (for my input with seven million marbles this equates to around 86MB of RAM) and keep a pointer to it:

let
    hundredMarbles = marbles * 100
    memory = alloc(MarbleSize * hundredMarbles)

Then when it comes to creating a “new” Marble, we simply calculate the position in our memory block and use it as a pointer:

proc addressOf(memory: pointer, marbleNumber: int): Marble {.inline.} =
    cast[Marble](cast[uint](memory) + cast[uint](marbleNumber * MarbleSize))

proc insertAfter(node: Marble, memory: pointer, value: int): Marble {.inline.} =
    var newNode = memory.addressOf(value)

Changing to this one-time allocation more than halved the runtime of the program, placing it firmly under the 100ms target I was aiming at. It’s particularly pleasing how little effort was required for optimisations like this, and how you can switch from high-level Python-style code to low-level C-style pointer manipulation.

You can find the full code to my solution in my aoc-2018 repository. If you’re not taking part in Advent of Code I highly recommend it, and if you’ve not used Nim it’s definitely worth a look.

PHP has always been fast to start, due to its primary use in a CGI environment, and the last few major versions of PHP have made its unbelievably blazingly fast as well, while Python unfortunately has issues with startup time ↩︎

Why you should be using HTTPS

2016-06-17T00:00:00Z

The EFF’s HTTPS Everywhere logo

One of my favourite hobbyhorses recently has been the use of HTTPS, or lack thereof. HTTPS is the thing that makes the little padlock appear in your browser, and has existed for over 20 years. In the past, that little padlock was the exclusive preserve of banks and other ‘high security’ establishments; over time its use has gradually expanded to most (but not all) websites that handle user information, and the time is now right for it to become ubiquitous.

Why use HTTPS?

There are numerous advantages to using HTTPS, both for the users of a website and for the operator:

Privacy

The most obvious advantage is that HTTPS gives your users additional privacy. An insecure (HTTP) request can potentially be read by anyone on the same network, or the network operators, or anyone who happens to operate a network along the path between the user and the server.

Users on shared WiFi networks (such as those in coffee shops, hotels, or offices) are particularly vulnerable to passive sniffing by anyone else on that network. If the network is open (as is frequently the case) then anyone in radio range can see exactly what the user is up to.

Integrity

HTTPS also helps to maintain the integrity of your site. With a plain HTTP request, there’s nothing to stop anyone in between the server and the user from modifying the content of the request or the response. This is a frequent tactic used by annoying WiFi gateways (such as the ones you’d find in a hotel), dubious ISPs who want to serve you extra adverts, or just plain old nefarious attackers.

If you’re trying to convey some kind of information to users (and if you aren’t, why exactly are you running a website again?) it seems beneficial to both you and them if the information arrives as you intended, rather than in a modified form due to someone or something tampering with it.

Security

If your website has any kind of authentication, or session identifiers, it becomes extremely vulnerable to an attacker monitoring the traffic and stealing the credentials. This was starkly demonstrated in 2010 when Firesheep was released. This tool allowed anyone to quickly and automatically hijack social media accounts of anyone on the same network who was using HTTP to access them.

Even if your login pages are served over HTTPS, if you send a single session ID cookie over HTTP (such as a page you decided wasn’t particularly ‘important’) then an attacker can probably spoof the user’s session and gain full access to their account. Again, in the case of open WiFi networks that could be anyone in radio range.

Search engine rankings

Some search engines use HTTPS as a signal in their ranking algorithms. Google announced in 2004 that it was using the presence of HTTPS as a small positive signal, but that it may strengthen that signal over time as more and more websites switch to using a secure transport. It’s not unthinkable that at some point in the future there will be HTTPS-only search engines.

But… But… But…

There are lots of excuses for not implementing HTTPS. Most of them are either misguided or outdated.

It’s too expensive and/or complicated

In the past, getting HTTPS certificates was a pain. A number of free suppliers have existed for a while but the process for getting their certificates wasn’t particularly straight forward, and many imposed arbitrary restrictions on the certificate parameters. Even once you had the certificate, you had to fiddle about with your HTTP server configuration to make it work, remember to manually get a new certificate when the old one expired, and lots of other annoying busywork.

With the arrival of Let’s Encrypt, all that changed. You can retrieve and deploy a free HTTPS certificate with two or three commands. Renewal can be handled completely automatically with a single command executed by cron.

There’s no point; nothing on my site is sensitive

You might not think your content warrants privacy, but can you speak for everyone who accesses it? Even content that seems mundane to you — such as travel advice, or technical writing — could be used to build up a profile of a user. If an attacker is monitoring traffic in a coffee shop and sees a user looking at travel advice and weather forecasts for a foreign country, he could use that information to plan a burglary knowing that the user will be away. Similarly, some content which is perfectly mundane to you may actually be very sensitive in other countries with repressive governments. HTTPS makes it much harder for these people to snoop on traffic.

From another angle, if you’re offering any kind of information, instructions, or especially file downloads, there’s a severe risk to users if the content is modified on its way to them. An evil sysadmin could rewrite your travel advice to suggest visiting the local drug dealer’s hangout, or replace your download with a malware-infested version.

HTTPS is slower, uses more resources, etc

Back in 1995 this might have been a valid argument. Enabling HTTPS on a modern server will make an almost negligible difference to performance. If you also enable HTTP/2 (which most implementations only support over HTTPS), it’s likely to actually use fewer resources, and result in a faster, smoother experience for your users. HTTP/2 was designed to work with HTTPS, and designed with modern requirements and networking techniques in mind.

CloudFlare have an excellent demonstration of the benefits of HTTP/2, and it can show speed improvements of 2-3x in a typical environment. On top of being faster, HTTP/2 uses fewer connections which results in less resource overhead on both the server and the client.

So what are you waiting for?

If you run a website and aren’t using HTTPS, give it a try.