The Domain Name System (DNS) is a fundamental piece of technology behind the modern internet. Thanks to its introduction in 1983, you're able to enter domain names like aezign.com.au instead of raw IP addresses in your browser's address bar and when sending emails. This article explains what it is, how it works, and how you can inspect your own website's DNS and ensure it is set up correctly.
DNS in a nutshellA well-used analogy is a phonebook; when you have someone's name and need to find their phone number, you look through the phonebook. Overall, DNS does the same thing: when you enter an address like example.com, your browser will contact a DNS server (the "phonebook") to determine its IP addresses. On Linux (or MacOS) systems, you can use dig on the command line to perform a DNS lookup and see what this looks like:
$ dig example.com
; <<>> DiG 9.20.29-1-Debian <<>> example.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 42782
;; flags: qr rd ra; QUERY: 1, ANSWER: 2, AUTHORITY: 0, ADDITIONAL: 1
;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 1232
;; QUESTION SECTION:
;example.com. IN A
;; ANSWER SECTION:
example.com. 221 IN A 104.20.23.154
example.com. 221 IN A 172.66.147.243
;; Query time: 20 msec
;; SERVER: 1.1.1.1#53(1.1.1.1) (UDP)
;; WHEN: Sun Sep 27 21:07:50 AWST 2026
;; MSG SIZE rcvd: 72
Here, you can see the DNS server being used is 1.1.1.1 (Cloudflare's DNS server), and that it found the IPs 104.20.23.154 and 172.66.147.243 associated with the domain name example.com. Your browser will then contact these IP addresses directly to load the website you are trying to open.
Configuring DNS serversYou can configure DNS servers through your operating system's network settings, and for some applications such as Firefox, with the application itself. If you don't manually set a DNS server, your computer will use the ones provided by your modem. If those are not configured, the default defined by the modem manufacturer or your ISP will be used.The most well-used and reliable DNS servers you can use are Cloudflare's (1.1.1.1 and 1.0.0.1) and Google's (8.8.8.8 and 8.8.4.4). Having more than one DNS server means that if the first one in the list doesn't work or doesn't find the matching IPs for a domain name, it will move to the next one in the list, a backup DNS server.DNS servers must be configured as IP addresses. If your computer tried to use a DNS server at a domain name, then where would your computer find the IP address for that domain name? It wouldn't be able to, as this is the exact gap that DNS servers fulfill.
RecordsDNS is not used only to find IPs for a domain, but a whole host of other things. Collectively they are referred to as "records" (or "DNS records"). Each record is associated to a domain (e.g. example.com) or a subdomain (e.g. bar.example.com, foo.bar.example.com) Here are some of the most common and important types:
A - Map to an IPv4 address (e.g. 104.20.23.154).This is the fundamental function of DNS: to map from a domain name to a server's IP address. Multiple A records leads to load balancing, where browsers will randomly select one of the returned IP addresses such that traffic is evenly split between them.
AAAA - Map to an IPv6 address (e.g. 2606:4700:10::6814:179a).This serves the same purpose as A records but for IPv6. Multiple AAAA records results in the same load balancing behaviour. All modern websites should have both an A record for legacy compatibility, and an AAAA record to future-proof for the gradual shift towards IPv6 addresses.
CNAME - Alias to another domain name (e.g. example.com).DNS servers will recursively lookup records for the aliased domain name until they reach an IP address (in an A or AAAA record).
MX - Specify a Mail Exchange server (e.g. mail.example.com).This record tells email SMTP servers where to direct emails to. For instance, the MX record for aezign.com.au is mail.aezign.au; this directs SMTP servers like Gmail and Outlook to send emails to the mailserver running at mail.aezign.au. This also allows specifying a priority field, so that you can define multiple MX records (such as a main and a backup) and consumers will try to connect to the listed mailservers from lowest priority to highest.
TXT - Store arbitrary text dataThis is most commonly used for site verification (for instance, to link your website to Google Search Console) and for email security measures like DKIM, DMARC, and SPF.
NS - Specify the nameservers for a domain (e.g. zeus.ns.cloudflare.com).These authoritative nameservers are responsible for providing all the other record types when needed.
dig lets you query each of these. For instance, to list the MX records against aezign.com.au:
Here you can see there is only one mailserver configured for aezign.com.au, which is mail.aezign.au, and it has a priority of 10.If you compare this against something like gmail.com:
You can see that gmail.com has several mailservers configured as redundancies due to the Gmail's sheer scale. gmail-smtp-in.l.google.com has the highest priority of 5, so SMTP servers will attempt to contact that mailserver first, followed by alt1.gmail-smtp-in.l.google.com and so on.
NameserversNow there needs to be somewhere for DNS records against a domain name to be defined, right? This is where nameservers come in.Nameservers are DNS servers that answer queries about the domains they are authoritative for i.e. the domains they are in charge of. For example, the authoritative nameservers for example.com are hera.ns.cloudflare.com and elliott.ns.cloudflare.com, which means Cloudflare's nameservers are the source of truth when looking up DNS records for example.com. You can check this with dig:
Nameservers are configured with your domain name's registrar. The nameserver you set dictates where your remaining DNS records will live. For example.com, this means you would configure all your records on Cloudflare's dashboard, since they are responsible for the domain's DNS records.
Recursive resolutionThe DNS servers that our computers use follow a recursive resolution process behind-the-scenes to find the authoritative nameservers for a domain, followed by the records you are querying.
Finding the root nameserversDue to the recursive nature of the resolution process, there needs to be a starting point: the root (.) nameservers. The resolver uses a fixed list of root nameservers called root hints issued by IANA (named.root), to locate and contact the root nameservers. Resolvers will have this provided to them initially, and can dynamically update it themselves by querying one of the root nameservers for the root NS records to obtain a fresh list. For instance, we can query 198.41.0.4 (a.root-servers.net) to obtain a new list of root nameservers:
$ dig @198.41.0.4 NS .
; <<>> DiG 9.20.29-1-Debian <<>> @198.41.0.4 NS .
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 43677
;; flags: qr aa rd; QUERY: 1, ANSWER: 13, AUTHORITY: 0, ADDITIONAL: 27
;; WARNING: recursion requested but not available
;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
;; QUESTION SECTION:
;. IN NS
;; ANSWER SECTION:
. 518400 IN NS l.root-servers.net.
. 518400 IN NS j.root-servers.net.
. 518400 IN NS f.root-servers.net.
. 518400 IN NS h.root-servers.net.
. 518400 IN NS d.root-servers.net.
. 518400 IN NS b.root-servers.net.
. 518400 IN NS k.root-servers.net.
. 518400 IN NS i.root-servers.net.
. 518400 IN NS m.root-servers.net.
. 518400 IN NS e.root-servers.net.
. 518400 IN NS g.root-servers.net.
. 518400 IN NS c.root-servers.net.
. 518400 IN NS a.root-servers.net.
;; ADDITIONAL SECTION:
l.root-servers.net. 518400 IN A 199.7.83.42
l.root-servers.net. 518400 IN AAAA 2001:500:9f::42
j.root-servers.net. 518400 IN A 192.58.128.30
j.root-servers.net. 518400 IN AAAA 2001:503:c27::2:30
f.root-servers.net. 518400 IN A 192.5.5.241
f.root-servers.net. 518400 IN AAAA 2001:500:2f::f
h.root-servers.net. 518400 IN A 198.97.190.53
h.root-servers.net. 518400 IN AAAA 2001:500:1::53
d.root-servers.net. 518400 IN A 199.7.91.13
d.root-servers.net. 518400 IN AAAA 2001:500:2d::d
b.root-servers.net. 518400 IN A 170.247.170.2
b.root-servers.net. 518400 IN AAAA 2801:1b8:10::b
k.root-servers.net. 518400 IN A 193.0.14.129
k.root-servers.net. 518400 IN AAAA 2001:7fd::1
i.root-servers.net. 518400 IN A 192.36.148.17
i.root-servers.net. 518400 IN AAAA 2001:7fe::53
m.root-servers.net. 518400 IN A 202.12.27.33
m.root-servers.net. 518400 IN AAAA 2001:dc3::35
e.root-servers.net. 518400 IN A 192.203.230.10
e.root-servers.net. 518400 IN AAAA 2001:500:a8::e
g.root-servers.net. 518400 IN A 192.112.36.4
g.root-servers.net. 518400 IN AAAA 2001:500:12::d0d
c.root-servers.net. 518400 IN A 192.33.4.12
c.root-servers.net. 518400 IN AAAA 2001:500:2::c
a.root-servers.net. 518400 IN A 198.41.0.4
a.root-servers.net. 518400 IN AAAA 2001:503:ba3e::2:30
;; Query time: 476 msec
;; SERVER: 198.41.0.4#53(198.41.0.4) (UDP)
;; WHEN: Mon Sep 28 00:01:08 AWST 2026
;; MSG SIZE rcvd: 811
Querying the root nameserversFor example.com, the first step is to query the root (.) nameservers to find the nameservers for the .com top-level domain (TLD). Using a.root-servers.net again:
$ dig @198.41.0.4 NS com
; <<>> DiG 9.20.29-1-Debian <<>> @198.41.0.4 NS com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 22528
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 13, ADDITIONAL: 27
;; WARNING: recursion requested but not available
;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
;; QUESTION SECTION:
;com. IN NS
;; AUTHORITY SECTION:
com. 172800 IN NS l.gtld-servers.net.
com. 172800 IN NS j.gtld-servers.net.
com. 172800 IN NS h.gtld-servers.net.
com. 172800 IN NS d.gtld-servers.net.
com. 172800 IN NS b.gtld-servers.net.
com. 172800 IN NS f.gtld-servers.net.
com. 172800 IN NS k.gtld-servers.net.
com. 172800 IN NS m.gtld-servers.net.
com. 172800 IN NS i.gtld-servers.net.
com. 172800 IN NS g.gtld-servers.net.
com. 172800 IN NS a.gtld-servers.net.
com. 172800 IN NS c.gtld-servers.net.
com. 172800 IN NS e.gtld-servers.net.
;; ADDITIONAL SECTION:
l.gtld-servers.net. 172800 IN A 192.41.162.30
l.gtld-servers.net. 172800 IN AAAA 2001:500:d937::30
j.gtld-servers.net. 172800 IN A 192.48.79.30
j.gtld-servers.net. 172800 IN AAAA 2001:502:7094::30
h.gtld-servers.net. 172800 IN A 192.54.112.30
h.gtld-servers.net. 172800 IN AAAA 2001:502:8cc::30
d.gtld-servers.net. 172800 IN A 192.31.80.30
d.gtld-servers.net. 172800 IN AAAA 2001:500:856e::30
b.gtld-servers.net. 172800 IN A 192.33.14.30
b.gtld-servers.net. 172800 IN AAAA 2001:503:231d::2:30
f.gtld-servers.net. 172800 IN A 192.35.51.30
f.gtld-servers.net. 172800 IN AAAA 2001:503:d414::30
k.gtld-servers.net. 172800 IN A 192.52.178.30
k.gtld-servers.net. 172800 IN AAAA 2001:503:d2d::30
m.gtld-servers.net. 172800 IN A 192.55.83.30
m.gtld-servers.net. 172800 IN AAAA 2001:501:b1f9::30
i.gtld-servers.net. 172800 IN A 192.43.172.30
i.gtld-servers.net. 172800 IN AAAA 2001:503:39c1::30
g.gtld-servers.net. 172800 IN A 192.42.93.30
g.gtld-servers.net. 172800 IN AAAA 2001:503:eea3::30
a.gtld-servers.net. 172800 IN A 192.5.6.30
a.gtld-servers.net. 172800 IN AAAA 2001:503:a83e::2:30
c.gtld-servers.net. 172800 IN A 192.26.92.30
c.gtld-servers.net. 172800 IN AAAA 2001:503:83eb::30
e.gtld-servers.net. 172800 IN A 192.12.94.30
e.gtld-servers.net. 172800 IN AAAA 2001:502:1ca1::30
;; Query time: 772 msec
;; SERVER: 198.41.0.4#53(198.41.0.4) (UDP)
;; WHEN: Mon Sep 28 00:09:25 AWST 2026
;; MSG SIZE rcvd: 828
Querying the TLD nameserversNow the resolver has .com nameservers and their IPs. We can use one of these, such as 192.5.6.30 (a.gtld-servers.net) to find the nameservers for example.com:
$ dig @192.5.6.30 NS example.com
; <<>> DiG 9.20.29-1-Debian <<>> @192.5.6.30 NS example.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 37419
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 2, ADDITIONAL: 13
;; WARNING: recursion requested but not available
;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
;; QUESTION SECTION:
;example.com. IN NS
;; AUTHORITY SECTION:
example.com. 172800 IN NS hera.ns.cloudflare.com.
example.com. 172800 IN NS elliott.ns.cloudflare.com.
;; ADDITIONAL SECTION:
hera.ns.cloudflare.com. 172800 IN A 108.162.192.162
hera.ns.cloudflare.com. 172800 IN A 172.64.32.162
hera.ns.cloudflare.com. 172800 IN A 173.245.58.162
hera.ns.cloudflare.com. 172800 IN AAAA 2606:4700:50::adf5:3aa2
hera.ns.cloudflare.com. 172800 IN AAAA 2803:f800:50::6ca2:c0a2
hera.ns.cloudflare.com. 172800 IN AAAA 2a06:98c1:50::ac40:20a2
elliott.ns.cloudflare.com. 172800 IN A 108.162.195.228
elliott.ns.cloudflare.com. 172800 IN A 162.159.44.228
elliott.ns.cloudflare.com. 172800 IN A 172.64.35.228
elliott.ns.cloudflare.com. 172800 IN AAAA 2606:4700:58::a29f:2ce4
elliott.ns.cloudflare.com. 172800 IN AAAA 2803:f800:50::6ca2:c3e4
elliott.ns.cloudflare.com. 172800 IN AAAA 2a06:98c1:50::ac40:23e4
;; Query time: 80 msec
;; SERVER: 192.5.6.30#53(192.5.6.30) (UDP)
;; WHEN: Mon Sep 28 00:12:19 AWST 2026
;; MSG SIZE rcvd: 359
Finding the domain's nameserverThe response tells the resolver that the nameservers for example.com are hera.ns.cloudflare.com and elliott.ns.cloudflare.com. Now since these Cloudflare nameservers are also .com domains and Cloudflare is so commonly used, the .com nameserver provides optional sibling glue records as defined in RFC 9471 to prevent further roundtrips and optimize the process.If we ignore the sibling glue records provided, the resolver would have to ask the .com nameservers for the nameservers for cloudflare.com:
$ dig @192.5.6.30 NS cloudflare.com
; <<>> DiG 9.20.29-1-Debian <<>> @192.5.6.30 NS cloudflare.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 40307
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 5, ADDITIONAL: 21
;; WARNING: recursion requested but not available
;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
;; QUESTION SECTION:
;cloudflare.com. IN NS
;; AUTHORITY SECTION:
cloudflare.com. 172800 IN NS ns3.cloudflare.com.
cloudflare.com. 172800 IN NS ns5.cloudflare.com.
cloudflare.com. 172800 IN NS ns4.cloudflare.com.
cloudflare.com. 172800 IN NS ns6.cloudflare.com.
cloudflare.com. 172800 IN NS ns7.cloudflare.com.
;; ADDITIONAL SECTION:
ns3.cloudflare.com. 172800 IN A 162.159.0.33
ns3.cloudflare.com. 172800 IN A 162.159.7.226
ns3.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:21
ns3.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:7e2
ns5.cloudflare.com. 172800 IN A 162.159.2.9
ns5.cloudflare.com. 172800 IN A 162.159.9.55
ns5.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:209
ns5.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:937
ns4.cloudflare.com. 172800 IN A 162.159.1.33
ns4.cloudflare.com. 172800 IN A 162.159.8.55
ns4.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:121
ns4.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:837
ns6.cloudflare.com. 172800 IN A 162.159.3.11
ns6.cloudflare.com. 172800 IN A 162.159.5.6
ns6.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:30b
ns6.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:506
ns7.cloudflare.com. 172800 IN A 162.159.4.8
ns7.cloudflare.com. 172800 IN A 162.159.6.6
ns7.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:408
ns7.cloudflare.com. 172800 IN AAAA 2400:cb00:2049:1::a29f:606
;; Query time: 163 msec
;; SERVER: 192.5.6.30#53(192.5.6.30) (UDP)
;; WHEN: Mon Sep 28 00:26:53 AWST 2026
;; MSG SIZE rcvd: 573
Here, the .com nameserver provides in-domain glue records for cloudflare.com's nameservers. Without these, there would be a circular dependency, since the nameserver named is a subdomain of the domain being queried for. This is because nameservers are always defined by name, which means that in order to actually contact the nameserver, your computer needs to obtain its IP address with another DNS lookup.Next, we'd use one of these nameservers, say ns3.cloudflare.com, to obtain the IP for hera.ns.cloudflare.com:
$ dig @162.159.0.33 hera.ns.cloudflare.com
; <<>> DiG 9.20.29-1-Debian <<>> @162.159.0.33 hera.ns.cloudflare.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 16801
;; flags: qr aa rd; QUERY: 1, ANSWER: 3, AUTHORITY: 0, ADDITIONAL: 1
;; WARNING: recursion requested but not available
;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 1232
;; QUESTION SECTION:
;hera.ns.cloudflare.com. IN A
;; ANSWER SECTION:
hera.ns.cloudflare.com. 86353 IN A 108.162.192.162
hera.ns.cloudflare.com. 86353 IN A 173.245.58.162
hera.ns.cloudflare.com. 86353 IN A 172.64.32.162
;; Query time: 123 msec
;; SERVER: 162.159.0.33#53(162.159.0.33) (UDP)
;; WHEN: Mon Sep 28 01:11:37 AWST 2026
;; MSG SIZE rcvd: 99
Querying the domain's authoritative nameserverNow we've reached the authoritative nameserver for example.com! The last thing to do is to fetch the A record for example.com to obtain its server's IP address:
$ dig @108.162.192.162 example.com
; <<>> DiG 9.20.29-1-Debian <<>> @108.162.192.162 example.com
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 43082
;; flags: qr aa rd; QUERY: 1, ANSWER: 2, AUTHORITY: 0, ADDITIONAL: 1
;; WARNING: recursion requested but not available
;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 1232
;; QUESTION SECTION:
;example.com. IN A
;; ANSWER SECTION:
example.com. 300 IN A 104.20.23.154
example.com. 300 IN A 172.66.147.243
;; Query time: 123 msec
;; SERVER: 108.162.192.162#53(108.162.192.162) (UDP)
;; WHEN: Mon Sep 28 01:13:47 AWST 2026
;; MSG SIZE rcvd: 72
At last, we've determined that the IP addresses of the servers behind example.com are 104.20.23.154 and 172.66.147.243. This matches our earlier lookup directly against your computer's configured DNS server.The DNS servers your computer uses employ this recursive resolution technique behind the scenes, so that your computer only needs to make one round trip, and the servers can use their much faster data center connections and caching to optimize the process and make the query as fast as possible.
Verify your DNS recordsTo check your website's records, the first thing you'll want to do is ensure your domain name is pointed at the correct nameserver. For instance, aezign.com.au is supposed to use Cloudflare, since that is where all the DNS records have been set up. We can verify this using dig, (or alternatively with online tools like dnschecker.org):
If this is not set correctly, the DNS records you configure will not work, as resolvers will be fetching records from somewhere else. In most cases, you can update this in your domain registrar's settings. This is especially common for new domain names, which default to the registrar's nameservers; unless you plan to use their built-in DNS management, you'll need to point them to your chosen provider.Now we can check that the DNS records you've configured match those your DNS server returns. For aezign.com.au, these are the MX and TXT records configured on Cloudflare. The MX record and some TXT records configured for aezign.com.au on Cloudflare's dashboard.We can check these using dig, and using the +short option to show only the content of the records.
As we can see, this matches, which means that the nameservers for aezign.com.au are correct and the DNS records are what we intend them to be.Note that if you've recently changed the nameserver or DNS records for your domain, it can take anywhere between 10 seconds and 24 hours for the changes to take effect and propagate across the different DNS servers worldwide. Tools like dnschecker.org can check your records on different DNS servers worldwide to see if they're reflecting your changes. The reason for this is caching: DNS servers like 1.1.1.1 will cache results so it doesn't have to do the full resolution process every time, and uses the Time-To-Live (TTL) you configure in your DNS records as a guideline for caching duration.
A library transition can affect
many packages in Debian. I added a way for Salsa CI to rebuild the ones that
depend on the changing library, so maintainers can test the transition before
it reaches unstable.
The need for this became clear during a proposed
Poppler transition. Poppler is a library
for rendering PDFs. The reverse-dependency job I had added to Salsa CI queued
100 of 115 candidate rebuilds, even though only about 21 were relevant.
The problem was documented in issue
#571.
Before this change, ratt used every binary package produced by Poppler to
decide what to rebuild. That also picked up packages unrelated to the library
transition. The tracker listed the old and new library package names, so I used
them to focus the selection.
The Poppler transition tracker identifies the old and new runtime library package names.
I added -transition_affected to
ratt to implement this selection. The
option performs the scan against the selected archive indexes and injects
locally built .deb files into each source rebuild. It expects a regex of
dependency package names, not a complete Ben expression, so the tracker s
Affected expression must be adapted first.
I then integrated the mode into Salsa
CI.
Maintainers can enable transition-aware
rebuilds
by setting SALSA_CI_BUILD_REVERSE_DEPENDENCIES_TRANSITION_AFFECTED_REGEX. If
the variable is unset, the pipeline keeps the existing selection.
A Poppler test showing the selected rebuild jobs. Three jobs reached the CI timeout, they were not confirmed package regressions.
I also changed ratt to cover
packages targeting
experimental. By default, it
resolves and rebuilds reverse dependencies from unstable while still injecting
the locally built .deb files. This lets a maintainer test a transition staged
in experimental against packages currently in unstable.
Together, these changes help maintainers focus CI on packages relevant to a
library transition and review rebuild results before the new library reaches
unstable.
Ode to the Half-Broken is a standalone post-apocalyptic (sort of)
science fiction novel.
As this novel opens, the unnamed first-person protagonist is waking up in
a bathtub in an abandoned building. They are covered in electromagnets and
missing one leg.
Waking up involved a secure reboot from a protected core kernel, so it is
immediately obvious that the protagonist is a robot. That also explains
the electromagnets, which interfere with their ability to control their
body. Or they would, if the protagonist didn't have long-dormant combat
routines available to deploy EM shielding and free themselves from the
bathtub. There are no immediate answers to why someone embedded a virus in
the data attached to a scientific paper on ants, an act so precisely
targeted that it had to be personal. Or what happened to their leg.
"There are a number of electromagnets in the next room," I say. I
point. "Behind that wall with all the holes in it."
"Those are big holes. And fresh, too," the dog says. "I wonder what
made them."
"Electromagnets experiencing sudden velocity."
The dog gives another of its short barks, and I am more convinced now
it is laughing, though I was not attempting to be funny.
Ode to the Half-Broken has a classic science fiction beginning:
in medias res in a future science fiction version of Earth where
nothing is immediately explained, leaving the reader to work out the date
and the setting. Helping us out is the protagonist, who is neither chatty
nor very sociable with other characters but keeps up an analytical
monologue about the world as they narrate events.
We are some decades into a grim future. The United States has largely
collapsed. Large parts of New York City are dangerous to humans due to
disease and radiation. Neither of those hazards bother the large number of
sentient robots; their scarcity, and therefore economy, is instead based
on power. Robots that control solar power stations act as low-level mob
bosses, trading power for information or labor.
Our protagonist doesn't want to care about any of this. They retreated
from the world long ago for a solitary life in the former New York
Botanical Gardens studying ants. But they need a new leg and the best
robot repair person nearby is a human woman outside of the city, so they
reluctantly head in that direction, accompanied somewhat surprisingly by a
cyborg dog.
The typical science fiction apocalypse is caused by something specific.
Classically, that event is a nuclear war, but writers found various
alternatives before, during, and after the Cold War era:
alien invasions,
meteor
showers, plagues,
sea level rise, and peak oil and general environmental collapse, among many others. Less
common is a post-apocalyptic novel where the collapse comes from multiple
overlapping crises and accumulating failures, from a general failure to
meet what Adam Tooze and others call
polycrisis. The first
time I encountered that style of post-apocalyptic story was in Octavia
Butler's Parable of the Sower. It was
one of the choices that made (and still makes) that book feel so
chillingly realistic.
The world background in Ode to the Half-Broken is shaped by that
sort of polycrisis collapse. There is no one reason why New York City is a
dangerous, irradiated ruin and society has collapsed into isolated and
sometimes warring factions. It is not runaway artificial intelligence, or
at least not directly; sentient robots were a late-stage innovation of the
collapsing US civilization and a tool and accelerator of its many wars,
but they were not the cause and may be a critical ingredient in building
some functional replacement. Instead, society fell apart because we failed
to address any of the growing problems and then turned on each other in
the resulting ruins. The reader gets an idiosyncratic view of that
collapse in flashback chapters intermixed with the main narrative of the
initially unnamed robot protagonist, flashbacks told from the perspective
of the man who invented the key component for robot sentience. As you
would expect, those two narratives are linked. The reader will not
discover how they are linked until late in the story.
This book could have been extremely depressing. It is not, which says a
great deal about Palmer's skill in telling it. The clinical distance of
the protagonist in the early chapters helps considerably: They have
rejected involvement in this world and therefore can describe it in
detached, factual terms, aided by the tendency of most robots in this
story to be slightly more precise, logical, and verbose than the human
characters. But as the protagonist's clinical distance fades, as it must
to allow the story's emotional stakes to rise, Palmer fills this book with
moments of beauty and hope. A former nuclear submarine that has become the
mind of a subway car is a key early ally. A collective has turned the
Hudson Bridge into a thriving if chaotic community. Self-regulating
enclaves of humans and robots are working together to try to build a
livable world. Robots oversee pollinator swarms that are attempting to
restore plant life, for no reason other than that they like order and
stability and see this as a way of restoring both. This is a grim,
post-apocalyptic world that does not dwell on either the grimness or the
apocalypse. It is instead full of small moments of hope, collaboration,
and personal connection.
This is a story with villains, danger, pain, and risk. Despite the similar
keywords and cover aesthetics, it bears little resemblance to Becky
Chambers's philosophical Monk and Robot series.
It is not, in any definition of the term, cozy; it's a post-apocalyptic
adventure story about a robot and a dog making their way through a ruined
civilization and fighting people who are trying to build something even
worse on the rubble. But it's also charming and oddly happy. There are
strong found-family vibes in the way that a party coalesces around the
protagonist and eventually gives them a name, there is the quiet happiness
of seeing a grumpy misanthrope slowly come out of their protective shell,
and the rail mechs are an absolute delight.
Like a lot of stories of happy small-group anarchism, I didn't entirely
believe the politics and have some qualms about the realism of the ending,
although perhaps I should strive to be as optimistic as Palmer writes. The
somewhat dry and fussily precise first-person narration will also not be
to everyone's taste; it worked for me by the end of the book, but it took
a bit of reading to get used to it. But those quibbles aside, this was
quietly lovely. It's a satisfying science fiction adventure story in a
world with disturbing parallels to the one we're living in, but which uses
those parallels to focus on small-scale collective efforts to build
something better. And all the small details of the world-building are
delightful: the different tiers of robots and their odd behaviors, the
machine sense of purpose, even the mix of suspicion and generosity. The
plot has large-scale implications, but it was the human-level details that
charmed me.
I still want another Fergus novel, but this was
a highly successful foray outside of that series. Palmer has won two Hugos
for her novellas, so I can't really say she's overlooked, but her novels
aren't getting anywhere near the attention they deserve. Highly
recommended.
There is plenty of world-building room here for a sequel, but Ode to
the Half-Broken reaches a satisfying standalone conclusion. So far as I
know, no sequel is currently planned.
Rating: 8 out of 10
In 2016, I removed Google Analytics from this blog to avoid being
complicit in feeding the biggest machine for harvesting personal data. Instead,
I relied on GoAccess to analyze my server logs.1 For the past couple
of years, the statistics have made no sense, despite my attempts to filter bots:
AI scrapers inflate the number of visitors to around 2,000 per
day. Eventually, I settled on GoatCounter, an open-source, privacy-friendly
web analytics platform. I replaced the JavaScript client to filter bots more
aggressively and added a CSS fallback. To improve reliability, I implemented a
local proxy running on each of the five web servers serving this blog. The rest
of this post details how these pieces fit together and how I deploy them on
NixOS.
Why GoatCounter?
GoatCounter does not collect personal data: instead of storing the reader s
IP address or relying on cookies, it creates a session identifier valid for 8
hours from the user agent and the IP address. Its feature set is modest but
sufficient for a blog. If you want to look at the interface, GoatCounter s
author runs a public instance for his site. A hosted
version lets you try it before running your own instance. With a single binary
and an SQLite database, GoatCounter is one of the lightest self-hosted
solutions. Privacy-friendly alternatives, in increasing order of complexity,
include Umami, Plausible, and Rybbit.
Custom JavaScript client
GoatCounter includes a small JavaScript client 2,189 bytes minified and
gzipped. It ships some features I don t use: a visitor counter, tracking clicks,
configurable settings, etc. I replace it with this function to register a hit:
If a reader has disabled JavaScript in their browser, I record the hit using a
CSS image. The :hover pseudo-class loads it only after an interaction, another
trick stolen from Bear Blog. About 2% of my visitors fit into this
bucket.3
<!DOCTYPE html><htmllang="en"class="nojs"><head><script>// The JavaScript code for this blog requires ES6if("noModule"inHTMLScriptElement.prototype)document.documentElement.classList.remove("nojs");</script></head><body><!-- ... --><style>.nojsbody:hoverborder-width:0;border-image:url('/count?p=/en/blog/2026-kpi-goodhart&t=Building...&r=NoJS&e=false');</style></body></html>
Where GoAccess reported around 2,000 visitors a day, GoatCounter counts fewer
than 200 humans.4 I assume AI scrapers use a low-effort approach: if the
content is available without barriers, as on this blog, they don t spawn a
complex mechanized browser that could trigger a page view. Even crawlers running
JavaScript, like Googlebot with its headless Chromium, do not
interact with the page and never trigger the events I listen
to. The interaction-based proof of humanity I use is likely to keep
working.5
Local proxy
Five servers across the world in Europe and in North
America serve the content of this website, but GoatCounter runs on only
one of them. To avoid losing track of visitors when GoatCounter is down, I run a
local proxy listening on the same /count endpoint. On each server, it stores
the hits in memory with a buffer large enough to survive several days of
downtime. It sends them in batches to the upstream backend using the
/api/v0/count authenticated endpoint.
Servers on a map. web02 is in Paris, web03 in Helsinki, web04 in Nuremberg,
web05 in Ashburn, web06 in Chicago.
I proposed the code for the proxy in pull request #909. GoatCounter s
maintainer declined to maintain so much code for such a niche use case. As a
fellow open-source developer, I often hold the same position for my own
projects: a one-time contributor effort may translate into a long-term
maintainer commitment.
I expose the endpoint for the proxy on the domain of this website to evade ad
blockers. This sounds like I don t respect the reader s choice, but as
GoatCounter is privacy-friendly, I find it acceptable.
Deploying on NixOS
My web servers run NixOS, a declarative Linux distribution with built-in
configuration management. I manage this small fleet with Colmena, a
stateless deployment tool for NixOS. My configuration is available on
GitHub.
Deploying applications in containers
For better isolation, each application runs inside an ephemeral lightweight
container, powered by systemd-nspawn. Each container runs a stripped-down
NixOS instance. A module wraps NixOS s containers options to
avoid repeating the same options for each application.6 The containers
share their network namespace with the host: the additional isolation is not
worth the increased complexity. For a smaller footprint, I also disable a few
non-essential services.
To configure a GoatCounter instance running in a container and listening on
127.0.0.4:8088, we import the module7 and declare the container in the
config.luffy.containers attribute set:
As the containers are ephemeral, we need to keep persistent data in directories
on the host. We add a mounts option and ask NixOS s containers to expose the
configured directories through the bindMounts option.
For example, to persist GoatCounter s database in the /var/db/goatcounter
directory on the host, we add the directory to the mounts option and alter the
service definition to tell GoatCounter where the database is.
A container may also need some secrets. Colmena can upload secrets without
storing them in the Nix store. We add a keys option to our containers. It
takes an attribute set mapping secret names to the commands to populate them.
Then, the module declares the required secrets to Colmena in the
deployment.keys option, makes the container depend on the presence of the
secrets, and exposes them to the container.
config, lib,... :letcfg= config.luffy.containers;in
options.luffy.containers= lib.mkOption type= lib.types.attrsOf (lib.types.submodule options=keys= lib.mkOption type= lib.types.attrsOf (lib.types.listOf lib.types.str);default= ;description="Secrets, as a command to run locally. They are mounted in /etc."; ; ; ); ;config=# Colmena uploads each secret in /var/keys and make them available# to the group "keys".
deployment.keys= lib.concatMapAttrs
(_: container: lib.mapAttrs
(_: keyCommand:inherit keyCommand;group="keys";permissions="0640";destDir="/var/keys"; )
container.keys)
cfg;# The container can only start if the required secrets are available.
systemd.services= lib.mapAttrs'
(name: container:letunits=map(key:"$ key-key.service")(lib.attrNames container.keys);in
lib.nameValuePair "container@$ name"requires= units;after= units; )
cfg;# Mount each secret inside the container.containers= lib.mapAttrs
(name: container:bindMounts= lib.mapAttrs'
(key: _: lib.nameValuePair "/etc/$ key"hostPath="/var/keys/$ key";isReadOnly=true; )
container.keys; )
cfg; ;
For example, GoatCounter needs credentials to download the GeoIP database. I
provide a local command to fetch the secret from my password manager and expose
it inside the container through the /etc/goatcounter.env environment file.
GoatCounter server
Nixpkgs already packages GoatCounter. By overriding the src and vendorHash
attributes, I reuse its definition for my custom version with the proxy:
I wrote a NixOS module to encapsulate GoatCounter: the
container definition, the service definition, and the secrets. The module
accepts the following options: package, serve.enable, serve.listenAddress,
serve.port, and serve.databaseFile. I already detailed the container
configuration in the previous section. In the end, I chose not to reuse the
GoatCounter module from NixOS: it s small, so it s better to insulate my module
from unexpected future changes.
config, pkgs, lib,... :letcfg= config.luffy.goatcounter;databaseDirectory=builtins.dirOf cfg.serve.databaseFile;chown="$ pkgs.coreutils/bin/chown -R";in
config.luffy.containers.goatcounter=
config.systemd.services.goatcounter=description="GoatCounter Web Analytics";wantedBy=["multi-user.target"];serviceConfig=EnvironmentFile="/etc/goatcounter.env";SupplementaryGroups=["keys"];DynamicUser=true;Restart="always";ExecStart= lib.escapeShellArgs [(lib.getExe cfg.package)"serve""-listen=$ cfg.serve.listenAddress:$ toString cfg.serve.port""-tls=none""-db=sqlite+$ cfg.serve.databaseFile""-automigrate"];# Transfer database ownership to dynamically assigned user "goatcounter".ExecStartPre="+$ chown goatcounter:goatcounter $ databaseDirectory";ReadWritePaths= databaseDirectory; ; ; ;
The following snippet configures GoatCounter to listen on 127.0.0.4:8088:
GoatCounter proxy
The same NixOS module configures the local proxy, with the
following options: proxy.enable, proxy.listenAddress, proxy.port, and
proxy.site the site receiving the batches of page views. The local proxy has
no persistent data, but it needs the API key to authenticate to the main
GoatCounter instance: its container uses the keys option but not the mounts
option.
config, pkgs, lib,... :letcfg= config.luffy.goatcounter;keyCommand= _:[" "];in
config.luffy.containers.goatcounter-proxy= keys."goatcounter-proxy.env"= keyCommand "GOATCOUNTER_API_KEY"; config.systemd.services.goatcounter=description="GoatCounter Proxy.";wantedBy=["multi-user.target"];serviceConfig=EnvironmentFile="/etc/goatcounter-proxy.env";SupplementaryGroups=["keys"];DynamicUser=true;Restart="always";ExecStart= lib.escapeShellArgs [(lib.getExe cfg.package)"proxy""-site=$ cfg.proxy.site""-listen=$ cfg.proxy.listenAddress:$ toString cfg.proxy.port""-ratelimit=10/1"# 10 requests per second per IP]; ; ; ;
For each server, I enable the local proxy with the following snippet. The
nginx configuration shown earlier exposes the /count endpoint under the same
domain as my blog.
Backup of the SQLite database with Litestream
Litestream is a streaming replication tool for SQLite databases. It
compresses the changes committed to the write-ahead log (WAL) next to the
database and sends them to a remote destination. I encapsulate its configuration
in a NixOS module, which takes an attribute set databases
mapping a name to the path of the database to back up.
Litestream also runs in a container. I mount the databases to replicate, as well
as the secrets to push the backups to a Hetzner storage box using SFTP:
We can restore the database from the backup with a few shell commands. First, we
stop the containers. Then, we move the damaged database away, invoke litestream
restore from the right environment, and restart the containers.9
Ten years after removing Google Analytics, JavaScript-based analytics is
back on this blog, but without storing cookies or IP addresses, and without
involving a third party. I still write for myself first, notably because it lets
me dig into a topic and refer back to it years later. But knowing a bit more
about my fellow human readers is a nice bonus, even the ones disabling
JavaScript.
Nginx scrambles IP addresses before storing them, thanks to the ipscrub
nginx module.
GoatCounter already filters some bots based on the user agent or the IP
address. But AI scrapers lie about their user agent and hide behind
residential proxies.
Without JavaScript, I cannot send the real referrer. I insert NoJS
instead.
I am missing the humans reading the RSS feed. I am not comfortable adding a
tracking pixel, and bots are likely to fetch it, compromising the
statistics. I ll live without counting these readers.
In February 2025, I tested another CSS-only approach without the interaction
trick: each page loaded an empty image as a background. Over a month, it
recorded up to ten times fewer page views than the nginx logs, even after
removing user agents identifying as bots. Compared to this experiment,
GoatCounter counts about three times fewer views, 18 months later. As the
time ranges differ, this is not an apples-to-apples comparison, but it gives
a hint about how efficient bot filtering is.
A NixOS module is a function receiving the configuration of the whole
system as config and returning three attributes:
imports adds other modules to import,
options declares user-configurable settings, each with a type and a default value, and
config sets values for options declared by any module, like containers from NixOS.
If a module does not need to declare options, you can return the config attribute
set directly. When a module does not require any argument, you can define it as an attribute
set instead.
Most of the time, you don t need an explicit import. NixOS automatically
imports the modules shipped with Nixpkgs. For my own
modules, some machinery also imports them automatically.
Litestream warns against using the auto-recover option as
it can cause data loss. But I don t properly monitor my servers and I prefer
uninterrupted backups to a slight chance of losing the last few records.
In my case, the process is slow: around 20 minutes for a 20 MiB database.
You can test by restoring to a copy with the -o option, but you still need
to stop the Litestream container.
It is said that those who cannot remember the past are condemned to
repeat it, a quote often attributed to the American philosopher George
Santayana. And to remember the past, records must be maintained and
kept accessible to learn from. With this in mind, it is no wonder
that archivists worldwide consider it crucial to ensure the archival
records are both complete and accurate, with a constant frustration
caused by the knowledge that the archives are neither due to
challenges in tracking down and collecting what should be
archived.
The last few days, I decided to simplify the collection of Messages
from the Mattermost chat
service, used by a few of the organisations I am involved in, to try
to improve the situation slightly. To achieve this, I had written a
dedicated extraction tool. Partly to see how hard it would be, and
partly to ensure that if one of the services were shut down or
replaced, everything in it would not be lost. Of course it is in the
nature of the use of instant messages that most of them are not fit
for permanent storage, at least not according to Norwegian law, where
there is a threshold "worthy of the archive" (arkivverdig) that should
be met, and messages like "should we go to lunch now" are below the
bar and should be filtered out. The tool can not help with this
filtering, and that will have to be done using other means after
collection.
The tools I had my bullshit generator write, under strict
supervision and many iterations, will extract every message visible to
the user whose credentials are used to log into Mattermost, and write
it out in Noark 5 extraction XML format and visualize the result. I
created the visualiser mostly to quickly be able to debug the
extracted XML, but also to make life easier for anyone interested in
testing out the tool set.
The extractor mattermost-noark5extract create a hierarchy
with arkiv/arkivdel for the Mattermost server, and then individual
mappe for each channel and direct message chat, a registrering for
each message thread, dokumentbeskrivelse for every message in the
tread, and one or more dokumentobjekt for each message and their
attachments/images. So far it is only tested on one Mattermost
installation, where around 23,000 messages is extracted in 61 seconds
and produce 295M with approximately 600 attachments and around 675,000
lines of XML in arkivstruktur.xml. You pass it the URL of the
service, a username and password, a directory path where to store the
collection and an optional channel name substring to limit the
collection to only a subset of the messages available.
The mattermost-noark5extract-browser viewer can load this
collection and visualize it similarly to Mattermost's web interface,
with the list of channels and direct messages dialogues on the left,
messages chronologically in the centre and a selected thread displayed
on the right.
I know Mattermost provide several login options. I've only had the
one used on my test server implemented so far, and know the extract
tool will have to be extended a bit for it to handle servers using one
of these options.
If you would like to examine the new toolkit,
mattermost-noark5extract
is available from gitlab. I wanted to put it on codeberg, but as
the recent rule change forbid code mostly written by a bullshit
generator there, it was not really an option. Note that some years
ago I wrote a similar tool to extract material from
the request
tracker system. The source for
request-tracker-noark5extract
is also available from codeberg. I would love to hear from you if
you test the tools.
As usual, if you use Bitcoin and wish to support my activities,
please send donations to
15oWEoG9dUPovwmUL9KWAnYRtNJEkP1u1b.
This is a new series1 I'm starting on the tools I have been crafting and
buying to play pedagogical games in my Economics classes.
These games, aside from being just plain fun for the students, often aim to
teach them a lesson via interactive play. Unsurprisingly, it is much easier for
them to grok a particular concept this way. Moreover, many students told me
these activities were the best part of the classes I teach.
The World Trade Game
I found out about The World Trade Game in The Handbook of Pluralist Economics
Education2, which also contains many other fun pedagogical games. It
was first developed by Action Aid, but has since been refined by John
Sloman and then by Irene van Staveren, who wrote about her use of the game in
the aforementioned book.
The goal of this blog entry is not to describe the game and teach you how to
play it. If that interests you, either buy the book I mentioned or read about
Sloman's version here.
No, our focus point here is the tools to play this game: fake cash! Fake cash
can be used in many economics pedagogical games and in my opinion, is a
worthwhile "investment" of your time and energy. You could indeed play with
regular printed sheets of paper listing a value (I sure did!), but using Play
Money (a more appropriate term, since we're not trying to defraud anyone) will
up your game and create a more immersive atmosphere in your classes.
At first, I tried to buy play money. Surely, some commercial offering aiming to
create realistic props for movies and TV productions existed? At least in
Canada, it turns out the answer was no. The only thing I could find were shady
websites and weird expensive listings on AliExpress. Not being tenured yet, I
did not try to convince my employer to take a 50-50 chance on supporting
criminal endeavours.
As such, the next best thing I found was printable play money designed by the
Bank of Canada Museum. Their designs were quite nice and met my needs,
but their PDF layout made it overly complicated to print large quantities of
bills. As such, I played around with GIMP a little and came out with these
files. A commercial printer shouldn't have issues printing them on glossy
cardstock paper and cutting them up for you:
Once printed and cut, you'll unfortunately have to fold each bill by hand. To
secure both halves, I ended up using a strip of transparent tape on each long
edge.
Here is the result, with a real Canadian 20$ bill as a comparison:
Don't hold your breath though, as I do not currently have a release
schedule.
Reardon, J. (2009). The Handbook of Pluralist Economic Education. New York : Routledge.
I ve long been interested in hardware key material storage devices. I ve been
a fan of yubikeys (I still remember
when my fancy new NEO-N showed up), PIV
(and its associated
smattering of
additionalfields),
SaaS HSMs,
the kernel keyring, some tooling
I ve fairly satisfied with the design of at prior companies, and of course,
our dear friend, the TPM. All that is not even to mention the scores of exotic
hardware security modules one generally comes across from time to time when
you re keeping a sharp eye out that you wind up playing with.
The concept of storing private key material on a disk, or even having it in
RAM has always skeeved me out, so I have a natural inclination to hardware
modules, and how shifting keying material around can change your risks
and threat model(s) in interesting ways.
I don t remember when I first came across the
MIFARE DESFire EV3, but a few weeks ago
I did a deep-dive into the state of the art of authentication schemes using
ID cards. My complete overview of what tradeoffs exist is pretty extensive
(and likely not interesting to the vast majority of the world), but the tl;dr
wound up being one of use PIV or use MIFARE DESFire EV3 . I wound up
picking DESFire for a recent project, and figured it s worth talking
a bit about what I learned, share some thoughts, and some code. That code is
published on crates.io/desox, and docs,
as is our custom, may be found at
docs.rs/desox
DESFire supports DES (I m sure most readers saw that one coming), 3DES (I
didn t bother playing with 3DES at all) or AES-128 (AFAICT always use this?)
keying material. It s worth noting that the DESFire only supports symmetric
keys and is not designed for public key cryptography, and operates exclusively
using shared symmetric key material. The DESFire EV series use those keys and
related authentication schemes to interact with files stored on the on-chip
EEPROM (2k, 4k, 8k, and 16k versions exist), or applications (groups of files
and authentication keys).
Talking to a DESFire EV3
Interactions with the card are done over NFC (ISO/IEC 14443 Type A), and
commands to/from the card may be in the usual ISO/IEC 7816-4 APDU format, or
unencapsulated bytes sent to/from the card are sent using a fixed instruction
set and return code structure saving a few bytes per message. I ve opted to
use their undocumented and proprietary format I found it easier to work
with and with a maximum message of 60 bytes, the savings matter a lot.
While powered via NFC, the card maintains a small amount of state about the
connection between the reader and the card in its RAM, including if the
session is authenticated or unauthenticated. I ll dig into how authentication
happens later, but it s worth knowing that sessions can become authenticated
using one of the symmetric keys shared by the card and the reader. The vast
majority of the
DESFire commands
I know about tend to work while either authenticated or unauthenticated,
with a few exceptions (GetUid, ChangeKey, and ChangeKeySettings
for example).
In general, I found working with this card particularly pleasant. There is a
fair amount of backwards-compatible behavior and multiple methods of
communication that confuse things a bit, but overall, it was better than
average to integrate with. Kudos to the NXP team. If the docs on this chip
were public, things would be orders of magnitude easier it s not entirely
clear to my why they re keeping so much of the interface documentation under
NDA, but it s the largest knock against the chip, by far.
Authentication
I found a lot of really great resources outlining how the handshake and
protocol works for a DESFire EV3, especially from
Ridrix,
some public datasheetsThrRealRevK
and posts from AndroidCrypto.
The gist here is that, because the DESFire only does symmetric key operations,
the key exchange (a type of SKA Symmetric Key Agreement) uses symmetric keys
to establish a unique session key which is used to sign or encrypt data
exchanged between the reader and the card. I m not going to get too in-depth
here, since there s a ton of other resources out there to dig into but I
will do a quick high-level description to keep this post mostly self-contained.
The authentication protocol serves two main functions to verify that both
parties know the same shared secret, as well as to act as a SKA to construct a
new session shared secret key. Here s a quick overview of how a shared session
key is derived between the reader and the card using our symmetric keys
(AES-128 in the case below).
the reader requests to start authentication with the card (something like
AA 00 to start an AES Authentication handshake with keyslot 0x00).
The card will then reply with AF (a status code that indicates more data
is to follow), followed by 16 bytes (in the case of AES-128) of encrypted
(using CBC) data.
The hosts then decrypts this block with the symmetric key from keyslot 0,
returning the card s session nonce.
The host generates 16 bytes (usually random) for its session
nonce.
The host sends an instruction of AF (indicating a continuation of
the previous command), followed by 32 bytes of encrypted data. When decrypted,
the first 16 bytes are our nonce generated in step #4, followed by the 16 bytes
provided by the card, decrypted in step #3, except where every byte is shifted
to the left by one place (the 0th byte is copied to the end).
The card will reply with 00 indicating a successful operation, followed
by 16 bytes, which when decrypted, is our session nonce from step #4, shifted
to the left by one byte in the same way that we did in step #5 with the card s
nonce.
At this point, both the reader and card have confirmed the other party has
the same symmetric secret key. The session is now authenticated and a
session key is derived using the two nonce blocks. Two hashing keys (K1
and K2) are derived from this key, which is used to maintain an ongoing
CMAC hash of the messages
coming and going to/from the card.
From here on out, the session is authenticated , and responses from the card
which were previously plain will now contain a 8-byte CMAC signature,
which can be used to ensure that the replies in question come from the
active session.
In my implementation of the handshake
I opted to encode the handshake state into rust types, just so I wouldn t make
any mistakes. The Handshake type contains the session internals (session
nonce values, keying state, to include IV, etc). This means the authentication
flow (from within my code) uses the Handshake struct to generate the commands
to send to the card in order:
/// Create a new Handshake , and return the
/// start auth command (something like AA 00 )
fnHandshake::<Initial>::begin(
output: &mut [u8],
key: [u8; 16],
key_id: u8,
) -> (Self, &[u8]);
After we get a reply back from the card (the encrypted version of the card s
session nonce, sometimes called Rnd_B in code I ve seen), we transition
states from Initial into HalfOpen.
/// Given the card's encrypted response, generate
/// our session nonce and generate a reply
/// (something that starts with AF followed by
/// 32 bytes of encrypted data).
fnHandshake::<Initial>::rnd_b(
self,
output: &mut [u8],
input: &[u8]
) -> (Handshake::<HalfOpen>, &[u8]);
Now that we re HalfOpen , we re waiting to hear back from the card to ensure
that it, too, can byte-shift our provided nonce. Once we have the card s reply,
we can check it using our complete helper, transitioning from HalfOpen to
Successful.
/// Check to ensure that the card replied with
/// our nonce byte-shifted by one place, indicating
/// that they know the symmetric secret in
/// this key slot.
fnHandshake::<HalfOpen>::complete(
self,
input: &[u8]
) -> Handshake::<Successful>;
Once the Handshake is successful, the only thing left to do is consume
the Handshake struct and turn it into the shared session key by running
it through the key derivation function.
/// Consume the Handshake struct and return the
/// new shared session secret key.
fnHandshake::<Successful>::into_key(self) -> [u8; 16];
From here on out we can use this session key for the remainder of our
interactions with the card signing messages from (and sometimes to!) the
card, or encrypted messages to and from the card. This key is used in CBC block
mode, where the session IV is updated with the last block of the encrypted
data.
Unit Testing
A nice proprietary of the SKA scheme we re using as part of DESFire is that the
derived session key is actually deterministic if you control your nonce RNG
(ok, actually, pretty true for most key agreements, but anyway), which means it
is possible to capture traffic over the NFC interface, and replay the NFC I/O
with cooked RNGs and ensure byte-identical messages and keys are generated.
Within desox-rs this is called replay (I m creative), and I ve got a few
replay sessions checked into VCS, which exercise a signficant amount fo the API
surface. All were derived from an actual session with a real DESFire card, and
can be updated with a live card and a --cfg flag.
Each replay file is a set of lines (request-response transactions), each
containing two space-delimited hex encoded NFC messages. For instance,
here s an authentication handshake in replay format:
The code that generated that exchange came from the test stored adjacent
to that file a handshake with the default DES key (all zeros), and
an RndA value hardcoded to 32c28fdafd3960de.
Since the card s RndB is similarly unchanging (I m replaying this file every
time), this will always derive the same session key, which means messages
(including encrypted ones or CMAC signed responses) will be identical, as well.
If you re playing with the DESFire yourself, feel free to grab my replay
files if you need a
known good baseline.
By default this will run using the
MockBackend,
replaying each file expecting a byte-identical request, and responding with
the harcoded customary reply. If the code (or test!) needs to change, updating
the tests is done by swapping the MockBackend out for a real one. Since I
had to do this a bunch during development, running cargo test
with RUSTFLAGS="--cfg desox_replay_rw" will, on run, overwrite the replay
file(s) for the executed test(s), ensuring all line-protocol changes are
explicitly caught and reviewed.
Observations
Most commands, even ones which require authentication, are transmitted without
CMAC signature(s) or encryption. CMAC signatures from the reader to the card
are not really used (except for writes to a file which specifies communication
must be CMAC signed), ditto for encryption (although that one is used for key
change operations, in addition to file writes on files that specify encrypted
communication must be used). The vast majority of commands take a plain
request from the reader, and return a CMAC signed response.
By my eye, this means that a malicious reader, or something otherwise capable
of holding the card online after communication with an authentic reader is
complete are able to execute privilaged commands (since one can simply ignore
the CMAC signatures on responses), so long as the command doesn t require the
reader to provide CMAC signatures (or encryption), or allow the card to power
down.
Fun with DESFire
I ve played around a bit with ways to use the DESFire cards in interesting
configurations, given what they re capable of. Here s some half-baked thoughts
I had while mucking around with the cards these are all poorly thought out
sketches of some things we can do given the specific tradeoffs I see with the
DESFire card. It s also worth noting that I don t have any of the actual
documentation, and am not a cryptographic grown-up, so take these sketches with
a massive grain of salt.
The first thing that came to mind when implementing this is how the
authentication scheme can shift the boundary of what is and is not trusted
(assuming good secure keying, and provided the key slots and card/application
permissions are configured correctly). Rather than push the key material out to
the machine connected to the NFC reader ( reader machine ), I instead tried
turning the NFC reader and computer into something psuedo-untrusted by merely
having it pass messages from the card to a trusted remote system ( remote
machine ). This means that the reader machine is exchanging NFC data with the
card, but that data is being decrypted, encrypted and processed by the trusted
remote machine the reader is unable to derive the session key.
For each of these, I wind up needing to authenticate so there s still a few
latent risks, but these can mostly be mitigated by asking for a readbacks of
any changed file(s), setting key permissions carefully, and requesting the
card s UID via the encrypted channel all of which would require the
symmetric secrets (which undermine the whole security model if comprimised).
This general construction is also subject to a hostile takeover of the
untrusted reader machine , since most commands (including destructive ones!)
are sent in PLAIN mode the reader machine can wait until authentication
is complete and then inject commands into the card and simply ignore the CMAC
signatures on responses, severing ties with the remote machine. As such, we
also need to take steps to ensure that the key being used is not one that
allows any access beyond what is allowed. Here were some ideas I sketched out
off the back of this theory.
The second-factor
Given some established (and authenticated) connection, part of the initial
authentication flow may use the DESFire card to prove physical control over it
as part of a handshake. This can serve as a second factor during some
authentication flow, requiring physical card presence at a reader to fully
initialize a connection. This does have one glaring downside, however it s
phishable. To use this for real , we d need to take some steps to prevent
obvious MITM flows (XOR the NFC messages with the URI as seen by the client?),
but maybe there s something interesting there.
This also has a second interesting attribute when used as part of a physical
system authentication flow, this becomes a logical place to inject access
control, being able to determine if some person is permitted to operate some
device at that particular time (Is Joe current on his Laser Cutter
certifications?) I think of the ideas I landed on, while conceptually
interesting (using an employee id card as a 2FA token, it s very fast), this
one is the least likely to turn into something real.
The encrypted-cookie
This construction, when paired with an encrypted DESFire file, allows the
remote machine to read/write an encrypted cookie to the card storing
small amount of encrypted data that the remote machine can read/write, but
not the reader machine , since this uses an encrypted and authenticated
channel from the remote machine directly to the DESFire card, without any
intermediate hosts needing to be fully trusted. I keep calling this the
encrypted cookie in my head because it feels conceptually similar to how Ruby
on Rails and Laravel handles cookies.
We d need to take a few extra steps here (for instance, ensure that you read
the cookie back over the encrypted channel after writing to prevent a malicious
reader from dropping writes) to secure the system, but it feels like the
structure of this is definitely decent.
The takeover
This time, let s say the computer attached to the NFC reader ( reader machine )
is semi-trusted. For this scheme, our trusted remote machine and the
reader machine pass messages over the network to handle authentication to the
card (as above), where the handshake data is being decrypted, encrypted and
processed by the trusted remote machine as usual. However, once the
authentication handshake is complete and a session key has been derived, the
remote system return the session key to the reader machine , giving it a
one-time-use key and authenticated session to the card.
We need to be careful about global/application permissions and key access
control to files but in this construction, we can allow the reader machine
to take over privileged actions using a scope-limited DESFire key without
handing over the card s true keying material (preventing cloning of the card).
This can be helpful to ensure messages to/from the card are truely from the
card (verifying CMAC signatures), enables the reader machine to directly
read/write to/from encrypted file(s), but allows the symmetric key material to
remain in as few places as possible which is critical given compromising
that secret will undermine the security of the entire system.
Vagrant Cascadian: Could you tell me a bit about yourself? What sort of things do you work on?
Jochen Sprickerhof:
I am a freelance programmer working on Open Source. Mainly doing Debian, F-Droid and some smaller software projects. In general I made it a habit to look into every software I use and try to fix bugs or add features I need. In Debian, I maintain about 180 packages with topics covering home banking, build systems and robotics. Most of my time, I currently work on reproduce.debian.net, where we try to bit-for-bit reproduce the packages distributed by Debian.
Vagrant: Could you describe the path that lead you to working on reproducible builds?
Jochen:
I started my Debian journey as a teenager, converting my school to Debian and serving as its system administrator for 13 years. After studying Applied System Science, I joined the university s robotics labs, where I worked on the Robot Operating System (ROS) and the Point Cloud Library (PCL). In the end, I enjoyed programming more than writing papers, so I eventually left academia for a robotics startup. Some years ago, I realized that the open source work I was doing in my spare time was actually the work I cared most about. Nowadays I am really grateful that I can spend my days working on things I find important and have lots of fun with.
Vagrant: What projects did you recently make big progress on?
Jochen:
A recent example is metasnap.debian.net. It is a meta archive of
snapshot.debian.org which is itself archive of all packages in Debian. But let
me explain it the other way round: with reproduce.debian.net, we try to reproduce the packages as they are distributed by the Debian archive. For that, we need the same build environment (compilers, libraries, build tools, etc) that was used by Debian back when the original package was compiled. Luckily, snapshot.debian.org has all those packages, but they are not easily accessible via apt, Debian s package manager. So, metasnap provides a mapping from a package name and version pair to the APT repo on snapshot.debian.org needed to download it from. It was created by josch some time ago, and it s awesome work. But when we tried to reproduce more and more packages on reproduce.debian.net, we found that some were missing packages from the build environment even though they where visible on snapshot.debian.org. We found that metasnap excluded some archive areas because they where not expected to be needed. Reimporting all the data took more than two months and surfaced a couple more flaws.
With this fixed, we were able to build more packages, only to find out that metasnap also needs better support for version numbers. Luckily we were able to rewrite the data in a day instead of starting the import again.
Vagrant: You have been working on infrastructure to support reproducible builds for a while. Has recent adoption of reproduce.debian.net into the Debian release tooling changed the focus of your work?
Jochen:
Quite a bit. When we started reproduce.debian.net in 2024, only around 33% of the packages could be reproduced successfully. Today we are above 98%. Most were not bugs in the packages themselves but in the infrastructure. Similar to the metasnap issue I reference above, packages just needed a rebuild because something else, like the toolchain, was fixed in the meantime. In May, people from the Debian release team and the Reproducible Builds project sat together and decided that the overall state is good enough, and now packages that regress on reproducibility are blocked from entering the next Debian release. But that does not mean all the work is on the shoulders of Debian package maintainers. Since then I have been constantly looking at the migration tooling to spot regressions and provide fixes. Furthermore, a couple of maintainers reached out to us for help and I hope more will do so in future.
Vagrant: What is one small thing you (or others) have not yet gotten to that you would really like to see?
Jochen:
The central tool to reproduce Debian packages is debrebuild, also written by josch. Currently it has two ways to retrieve the build dependencies of a package. Either it uses metasnap.debian.net (as explained above), or it can access the Debian unstable APT repository directly. This allows to test packages locally before everything is indexed on metasnap by compiling against Debian unstable. But actually there are many other APT repositories to query, like Debian stable or even derivatives. Adding support for an optional list of APT repositories in debrebuild would be great. That would also be a big step to support reproducing other Debian based distributions.
Vagrant: and one big thing?
Jochen:
It would be great to integrate metasnap.debian.net into snapshot.debian.org. There is some discussion on it already in Debian bug #650783.
Vagrant: What are the tools you use the most?
Jochen:
According to my fish shell history:
$ history cut -d' ' -f1 sort uniq -c sort -nr head -10
36199 git
20941 vi
12271 rm
8599 cd
7917 ls
6407 apt
5631 grep
4249 mv
3655 dpkg
2873 cp
Vagrant: So, is the fish shell reproducible? I remember it did not used to be
Jochen:
You can check for yourself it was last time I checked. But looking through the other commands, neovim sadly is not. I hope we can fix that in future.
Vagrant: Oh, that s a nice URL to check for reproducible package you can just pass the source package name to check the current results?
Jochen:
Yes. Another one is udd.debian.org/reproducibility/, where you
can list all packages of a Debian maintainer. It also lists source reproducibility and has nice filters as well.
Vagrant: What tools do you use specifically working on reproducible builds?
Jochen:
I don t have statistics for that, but I would say sbuild to build the package, debrebuild to reproduce it, and diffoscope to analyze the differences. Obviously I also need run apt source <package> or use git-buildpackage to get the sources and all the tools I mentioned above.
Vagrant: So how many packages are left to build reproducibly, and once those are finished, what is next?
Jochen:
Right now, reproduce.debian.net shows over 98% reproducibility, though there are still over 650 package left and some will probably need a lot of work. But actually I think making packages reproducible is just the first step. For me, this is a project to build confidence in the system. To reproduce a package we have two parts: the source of the package and the build environment. Fixing the packages means gaining confidence in the first part but we still rely on the individual build environments for each package as we need to use the same compiler that was used when the package was build initially. Because of this, we have to keep around every historical version of all toolchain packages. I really would like to remove this extra archive, which means we would have to rebuild all of Debian around release time. I am dreaming of a Debian release where you could bit-for-bit reproduce every package just from the released versions. Due to how Debian works, however, this is not a trivial rebuild and it would need some work on the infrastructure. By the way, initially there was a third component to pay attention to: any connection to the outside world during the build. Luckily we fixed the Debian build daemons to not allow network connections during the build some time ago.
Vagrant: Thanks for all that work, and taking the time to tell us a bit about yourself!
Jochen:
Thanks a lot for the interview!
For more information about the Reproducible Builds project, please see our website at
reproducible-builds.org. If you are interested in
ensuring the ongoing security of the software that underpins our civilisation
and wish to sponsor the Reproducible Builds project, please reach out to the
project by emailing
contact@reproducible-builds.org.
Replacing lxc with Incus for Debian CI, by Antonio Terceiro
At the beginning of this month,
the default backend for tests was changed to incus-lxc,
leaving only a few dozen packages explicitly configured to run as lxc. Those
packages got bug reports filed
and once those bugs are fixed they will be migrated over to incus-lxc. This
marks an important milestone for Debian CI, as the low level of isolation
between the worker host OS and the OS under test when using lxc was a
significant source of instability in our platform. Common causes for test
failures when comparing runs under plain lxc with runs with incus-lxc are
documented in the wiki page
linked from the bug reports.
security-tracker git performance, by Helmut Grohne
Developers working with Debian s security-tracker
have reporteddegrading
performance for a while. The options for solving this are few with repository
sizes now reaching 30GB for a repository whose working tree is a mere 60MB.
While there have been a number of proposals for changing the storage layout,
Helmut evaluated options not requiring such changes. Much of the problem hinges
on the 50MB data/CVE/list file that is updated in most commits. Efficiency
hinges on representing its content in git packs.
Practically, git frequently fails to represent its content as a delta and stores
a full copy that is typically compressed to 12MB. Add a few thousand 12MB full
blobs and you quickly have a large repository. In particular, the copy at
salsa.debian.org stores many such full blobs, so pulling from it consumes
significant bandwidth.
One might think that running git gc helps, but its utility is limited here.
When git stores objects in packs, it stores the
history in reverse.
It starts with the current version and represents older objects as differences
(deltas) to more recent objects. A delta effectively is a sequence of copying
ranges from a base object and insertion of new content. Given that humans tend
to add content over time, those additions are often represented as deletions.
The crux here is finding that base object. Given that the data/CVE/list file
is large, finding it involves comparing quite a few versions of it with each
other. This requires both a significant amount of RAM and CPU time. How many
objects git considers for this comparison is controlled with the --window
option. It is beneficial if the base object does not come from a direct child
commit but skips over commits. In doing so, long chains of deltas are avoided.
The --depth option controls the maximum chain length.
In this search, git combines all objects into a single window to facilitate file
renames. As such, it tends to compare data/CVE/list with data/DSA/list,
data/DLA/list and others. This is less than helpful and tends to evict all
data/CVE/list versions from the comparison window such that a new full blob of
it becomes required. Since the security-tracker repository rarely renames files,
we can ask git to instead consider one window per filename
via --path-walk. Once doing so, it becomes quite a bit better at finding
suitable deltas. The technique is less applicable to older history (2025 and
earlier), but given a lot of RAM and a bit of partitioning, git gc can shrink
that as well. Combining these techniques, we can shrink the repository into
700MB and keep new growth somewhat under control.
Temporarily, Helmut is providing a proof-of-concept mirror at
git://git.subdivi.de/~helmut/security-tracker.git using these techniques.
Avoid pulling from it directly as it does not provide a secure transport. While
it does reduce the amount of data being downloaded, it does not resolve a number
of related problems. After downloading, a git client will still expend
considerable amounts of CPU on verifying received deltas and attempting to
git blame data/CVE/list is not improved in any way. Still, there is work on
integrating some of the improvements back into salsa.
OpenSSH GSS-API split, by Colin Watson
In an option review
Colin did in 2024, shortly after the xz-utils backdoor,
he explained that having GSS-API authentication and key exchange support in the
main OpenSSH packages is problematic. The key exchange patch is large and
intrusive. Even linking to the necessary libraries isn t without risk: as the
Ebury malware attack demonstrated
way back in 2009, each extra library linked into security-critical daemons such
as sshd (or nowadays into its privilege-separated helper programs) can modify
the behaviour of the daemon even if you aren t doing anything that would involve
calling into that library. Of course some of that risk remains, but as
Damien Miller wrote,
minimizing the number of libraries that end up in the address space of sshd
and friends is still valuable.
This split is now complete in testing. As of openssh 1:10.4p1-5, the OpenSSH
client and server are built without GSS-API authentication and key exchange
support. If you need those features, install openssh-client-gssapi or
openssh-server-gssapi instead, as appropriate. Debian 13 (trixie) already has
packages with those names that just depend on the regular openssh-client and
openssh-server so that you can pre-emptively install them, as
documented in the release notes.
The new openssh-*-gssapi packages have relatively tight dependencies on
openssh-common, in order for the testing migration system to ensure that we
can t forget to keep them up to date. This will mean a bit more ongoing work on
each new upstream version, but it should be manageable.
Catching up on DebConf video publication, by Stefano Rivera
DebConf 25 videos suffered terribly
from a bug in voctomix that
stopped us from being able to publish the videos immediately after the
conference. Ivo De Decker did some work on the videos earlier this year, fixing
enough of the audio problems to make the videos at least intelligible.
While at MiniDebConf Winterthur Stefano
published all the videos from 2025 and 2026 to PeerTube
and YouTube.
DebConf 25 and DebConf 26 videos as well as all the videos from miniconfs that
had got caught up in the backlog were published.
Miscellaneous contributions
Carles used po-debconf-manager
to review and submit Catalan translations for six packages.
Carles prepared a prototype
of building webwml and running tidy (linter) in Salsa.
Carles created different webwml
merge requests
with different fixes: invalid links to different architectures, 404s to external
sites, fixed templates with invalid URL to favicon.ico, making USE_SAMPLE_FILES=1
to avoid fetching external files, typos in English, etc.
Antonio did several Salsa maintenance tasks,
including his first platform security update and investigating an issue that was
causing the background tasks to be severely delayed, imparting the site usability.
Thorsten tried to fix some bugs in hplip and cups. Unfortunately this did not
result in an upload this month, but stay tuned!
Helmut continued to report undeclared file conflicts and correspond about them.
Helmut reviewed and merged Johannes Schauer Marin Rodrigues work on adding
hurd support to debvm.
Helmut fixed a pile of minor issues in the support libraries underpinning
unschroot.
Helmut adapted rebootstrap to archive regressions and improved its handling of
non-default gcc versions.
Santiago continued helping Aryan Karamtoth with the GSoC project on
introducing livepatching support for linux. Several challenges have been
identified in the recent couple of months, and Santiago is trying to guide Aryan
to address them and design the solution. The mentoring is done in collaboration
with Emmanuel Arias.
Lucas onboarded a co-maintainer for Valkey.
Lucas has started to work on a draft for the Debian Outreach project for
onboarding newcomers interested in Debian packaging via a video course.
Stefano worked on the after-math of DebConf 26, handling the bursary expense
reimbursement process and winding down the conference finances.
Stefano uploaded Python 3.15 RC 1 to Debian unstable.
Stefano did some budgeting and travel planning for the DebConf 27 site-visit
in Asahikawa, Japan. The DebConf committee sends a couple of members to meet
with the local team and view the venue together, in advance of the next DebConf.
Welcome to the August 2026 report from the Reproducible Builds project!
In our reports, we try to outline the most important things that we have been up to over the past month. As a quick recap about what problem our project intends to solve, whilst anyone may inspect the source code of free software for malicious flaws, almost all software is distributed to end users as pre-compiled binaries. The motivation behind the reproducible builds effort is to ensure no flaws have been introduced during this compilation process by promising identical results are always generated from a given source, thus allowing multiple third-parties to come to a consensus on whether a build was compromised or not.
In this month s report, we cover:
New updated SBOM specification from CISA.gov
CISA, the Cybersecurity and Infrastructure Security Agency of the U.S. government published some the joint guidance entitled Minimum Elements for a Software Bill of Materials (SBOM), which updates and supersedes the baseline 2021 version covered in previous editions of these reports.
Whilst the PDF is worth skimming, the interesting changes include that the specification now mandates standard cryptographic hashes: unlike earlier standards that allowed hash omission or manifest-only parsing, hashes must be computed from the output. This is is important for reproducible builds, as it ensures the recording of the metadata required to demonstrate the shipped software matches the build output precisely where applicable. In addition, where the top-level only dependency limitation that was present in the 2021 version has been removed in favour of complete coverage with no minimum depth. That is, SBOMs are expected to reflect all linked libraries, vendored dependencies and other build-time inclusions.
The basic idea behind bootstrappable builds is to create a system that can be built without relying on pre-built artifacts. Can we go from zero to the modern day without having to just assume the existence of these already-built-for-us artifacts? The classic recipe for yogurt requires some yogurt to start the process, which is like how we normally build a C compiler today we start with an existing C compiler binary. You might think about making sourdough bread with your grandmother s starter brought over from the old country; we re basically making C compilers with Dennis Ritchie s starter carried over from Bell Labs .
The reason I like the idea of making reproducible builds work is that I think it can be done in such a way as to not require any work on the part of the producer of a distribution (which is a technical term for sdists or wheels, i.e., the people who upload stuff to PyPI), and thus make reproducible builds very low-friction for people to opt into supporting. []
Brett goes on to outline What s missing from the specs and how reproducibility might be visible on PyPI to consumers:
Assuming all of this comes to pass and we record the where the source code is that went into a distribution and the software used to make the distribution, how do we make it useful to people? Does every person who cares about having a secure supply chain have to rebuild everything they use themselves? Is there some way for even people who don t care about this stuff to benefit? []
Distribution work
In Debian this month, 23 reviews of Debian packages were added, 28 were updated and 27 were removed this month adding to our knowledge about identified issues. A number of issue types have been updated as well, such as the addition of a new toolchain issue related to python-traitlets [], and the note for an existing issue related to texi2html was updated as well [].
Lastly, Bernhard M. Wiedemann posted another openSUSEmonthly update for their reproducibility work there.
Unreproducible builds under EROFS filesystem fixed
Martin Pitt reported on Fosstodon that they had identified an issue where the mkfs ( make filesystem ) command for the EROFS (Enhanced Read-Only File System) subsystem of the Linux kernel did not have sorted extended file attributes, leading to reproducible builds.
Thankfully, Martin also reported that they had fixed this in a commit to the kernel which order[s] each inode s xattrs by name so that images stay reproducible . []
Tool and documentation development
diffoscope is our in-depth and content-aware diff utility that can locate and diagnose reproducibility issues. This month, Chris Lamb made a number of changes, including preparing and uploading versions 327, 328 and 329 to Debian. In particular, he ensured that diffoscope did not require python3-guestfs in the autopkgtests on 32-bit architectures in order to fix Debian bug (#1144372) []. Colin Watson made an additional change, handling a potentially missing openssh-client package when running the autopkgtests [], and Jochen Sprickerhof made a similar change to cope with missing cpio and qemu-img functionality [] whilst also updating the XML comparator to be considered when comparing SVG images [].
Yet again, there were a number of improvements made to our website this month as well. For example:
Chris Lamb added draft for a Gothenburg summit-related news article. [][]
Lastly, a large number of commits were pushed comprising an interview with Reproducible Builds developer Jochen Sprickerhof to be published within the next week. [][][][][][][]
Six new scholarly papers
Jens Dietrich, Spencer Sun, Tim W. White and Behnaz Hassanshahi (the result of a collaboration between Victoria University of Wellington and Oracle Australia published a paper this month entitled No Snake Oil: Verifying Python Package Builds. Drawing on the metaphor of snake oil , that is, a fake or ineffective medicine or solution sold with exaggerated claims of curing or fixing everything, the authors write that
Two tools that are designed to automate [PyPI] rebuilds and run them at scale are macaron and oss-rebuild. We study 12,180 popular releases from PyPI and find that the byte-for-byte equivalence rate is generally low. We analyse the reasons why they produce different wheels, and find that equivalence between the original and rebuilt wheels can often still be established, preserving most of the guarantees users expect from rebuildable releases. We present and evaluate daleq4py, a tool to establish the equivalence of Python wheels through the kernel of a normalisation function that is based on provenance-preserving datalog rules. Experimental results show that daleq4py substantially expands the set of rebuilds that can be accepted as equivalent.
pose a persistent threat to opensource software. Known attempts to inject such backdoors into widely used projects through malicious commits, tampered release packages, or compromised third-party dependencies, were stopped only by luck and manual review. Existing Continuous Integration (CI) pipelines cannot detect these attacks, and downstream binary analysis tools require substantial manual effort. In this work, we present Lily, an automated approach that strengthens open-source development and release processes against backdoor injection. Lily integrates a backdoor detection mechanism into (1) CI pipelines to block malicious commits, and (2) release vetting workflows to prevent tampered releases or compromised dependencies from entering large ecosystems, such as Linux distributions.
The full PDF can be read online.
Ranindya Paramitha and Laurie Williams of North Carolina State University along with Christian K stner of Carnegie Mellon University published a paper this month with the title of The Software Supply Chain as a Market for Lemons: A Multivocal Review of Trust Signal Collapse. (A lemon in American English, is a vehicle that turns out to have several manufacturing defects .) Their abstract is as follows:
Practitioners evaluating open-source dependencies rely on cheap trust signals, e.g., stars, download counts, and contributor activity, as substitutes for direct code inspection, assuming those signals reflect genuine trustworthiness. Prior work has documented individual signal gaming, but the landscape of collapses across all dependency-adoption signals, as well as the ecosystem s response, remains unexplored. The goal of this study is to aid software practitioners in understanding the reliability of dependency adoption trust signals, such as download counts and contributor activity, by conducting a multivocal review of 252 Google Search sources and 870 Reddit threads.
Worryingly, after their review, the authors conclude that cheap trust signals collapse under three simultaneous forces: adversarial manipulation, gaming techniques indistinguishable from legitimate behavior, and non-adversarial AI-driven inflation.
The full PDF of the paper is available online.
Julien Malka, Aman Sharma, Martin Monperrus, Stefano Zacchiroli and Th o Zimmermann published a paper this month on Trusting-Trust Attack against an Entire Linux Distribution through Binary Manipulation:
Ken Thompson s trusting-trust attack, in which a compromised compiler backdoors the programs it builds and reproduces the backdoor in subsequent rebuilds of itself, is widely regarded as a threat specific to compilers. We show that it is not. We construct a complete trusting-trust attack around GNU strip, an ordinary build utility that neither inspects nor generates source code, using only manipulations of finished ELF files.
Scarily, in the authors example, a single tampered strip in the binary seed implants a payload that propagates from one generation of strip to the next and survives into the final standard environment after the seed leaves the dependency closure [ ] without failures and backdoors .
A full PDF of the paper is available for download online.
Mehdi Keshanimm, Amirhossein Rahmati, Mohammad Hossein Aref and Abbas Heydarnoori published a paper that is currently under review at Emperical Software Engineering titled AROMA+: A Study of Factors Affecting Reproducible Builds in the Maven Ecosystem. (Maven is a/the build automation tool used for Java projects.) In their paper, the authors note that
[ ] reusing external software in a project presents a security risk when the source of the component is unknown or the consistency of a component cannot be verified. The SolarWinds attack serves as a popular example in which the injection of malicious code into a library affected thousands of customers and caused a loss of billions of dollars. [ ] Our research aims to support [reproducibility] efforts in the Maven ecosystem through automation. We investigate the feasibility of automatically finding the source code of a library from its Maven release and recovering information about the original release environment. Our tool, AROMA+, can obtain this critical information from the artifact and the source repository through several heuristics and we use the results for reproduction attempts of packages on Maven Central.
[A]rtifact verification requires more than deterministic builds: a verifier must also recover the source state, build environment, dependencies, and build instructions that produced the artifact. Decentralized-build ecosystems make this difficult because artifacts are produced through heterogeneous tools, maintainer-controlled workflows, and fragmented metadata. As a result, it remains unclear how often artifacts in these ecosystems can be independently verified. This paper studies artifact verifiability across four popular decentralized-build package ecosystems. We define an independent verifier model that relies only on registry-derivable metadata and an artifact comparison model with tiered equivalence levels. We implement these models in an Artifact Verification Pipeline and use it to measure artifact verifiability across the target ecosystems.
The authors conclude that beyond build determinism, verifiability is limited by missing source and build metadata, implicit release transformations, and unconventional build practices .
A PDF of their paper can be reviewed online.
Patches
The Reproducible Builds project detects, dissects and attempts to fix as many currently-unreproducible packages as possible. We endeavour to send all of our patches upstream where applicable or possible. This month, we wrote a large number of such patches, including:
I m looking at something entirely unrelated, but tripped over some search results that made me realise that a lot of people still think getting errors like ACPI Warning: SystemIO range 0x0000000000001828-0x000000000000182F conflicts with OpRegion 0x0000000000001800-0x000000000000187F indicate a firmware bug. This is generally untrue. We need to dive a little into what ACPI is to clarify why.
The Advanced Configuration and Power Interface1 specification defines a whole bunch of stuff, but what s interesting to us here is the hardware abstraction it performs. While PCs are nominally a well-defined platform that s really not true at the hardware level once you get beyond a certain level of complexity. When you suspend a system you want to power down the hardware in the correct order, for instance, and knowing what that order is requires you to know details about the specific motherboard design. The approach taken in the embedded world is to just bake that knowledge into the OS in some form, which is how we end up with Devicetree. ACPI takes an alternative approach - rather than provide that information as data that has to be consumed by OS drivers, it distributes it as code.
The ACPI Source Language, or ASL, is a simple language that gets compiled into a bytecode that s then interpreted by the OS at runtime. One of the features of this language is the ability to define Operation Regions , effectively structure definitions that describe access to underlying hardware. Let s imagine a simple device with two exposed registers. The first is an index register - it describes which internal register we want to access. The second is a data register, where reading it gives us the value of the internal register whose address is currently in the index register, and writing to it modifies that register. An example operation region declaration would look something like
This defines an operation region called OPR1 at IO port 0x400, 2 bytes long. Inside it are two 8-bit fields, INDX and DATA. These are to be accessed one at a time, do not need the ACPI interpreter to take a global lock when accessing them, and if a subset of the register is modified then the other values should be preserved (irrelevant in this case since the fields are only a byte wide). Now any references to INDX or DATA in this scope will trigger accesses to those registers. So, a method to read the value of register 0x03 would look something like:
1
2
3
4
Method (RD03)
INDX = 0x3
Return (DATA)
ie, set INDX to 3, and then read the value of DATA and return it. But! What if another ACPI method is running at the same time? Let s say we have one that writes to register 0x05:
1
2
3
4
Method (WR05, 1)
INDX = 0x05
DATA = Arg1
What happens if RD03 executes while we re part-way through WR05? INDX might get reset to 0x03, and now WR05 will modify register 0x03 instead of 0x05. Oh no! But we can avoid this - we declare a mutex (Mutex (MUTX, 0x00)), and update our methods to be something like:
Each method takes a lock (waiting up to 0xffff milliseconds and then erroring out if it doesn t), and performs the access. There s now no chance of a race. Phew!
Now suppose someone writes a Linux driver for this piece of hardware. It accesses the hardware directly, with no knowledge of ACPI. What stops the driver from racing against one of the ACPI access methods? Nothing at all. Oh no! Again! This isn t hypothetical, by the way - here s a relatively harmless example, but back in the day we did trip over cases where temperature monitoring chips would be accessed by the firmware and Linux simultaneously and as a result you might end up thinking you re reading a temperature when you re actually reading a status flag, resulting in an impossibly high temperature and an immediate thermal shutdown.
In this case, the kernel saves you from this (potentially hardware damaging) outcome by printing a message like ACPI Warning: SystemIO range 0x0000000000000400-0x000000000000401 conflicts with OpRegion 0x0000000000000400-0x0000000000000401 (OPR1), telling you that the kernel has detected that a driver is attempting to allocate IO ports 0x400-0x401, but that there s an ACPI operation region called OPR1 that is claiming the same addresses. The kernel isn t in a position to know what type of access the firmware might perform in that region, so assumes that it might be dangerous and blocks the driver from loading.
But all is not lost! The kernel also prints some helpful advice, ACPI: If an ACPI driver is available for this device, you should use it instead of the native driver. And ACPI tables will often actually have a definition that looks like this:
which defines an ACPI device and associated methods. The _HID field defines the device type, and a Linux driver can be written that will be automatically loaded if a device with type VEND0001 is seen. That driver can then call ACPI methods associated with the device and access the resources in a way that matches the firmware s expectations.
(Interested in writing such a driver? I wrote a guide back in 2009)
The firmware did absolutely nothing wrong here2, but trying to load the native driver will generate an error and the internet will tell you that PC firmware developers are incompetent3 and you should pass a kernel argument that overrides this behaviour and it never did them any harm, and it probably won t do you any harm either but it might and you might never know why your system occasionally wedges or catches fire.
The ACPI spec used to live at acpi.info, but sadly that seems to have vanished some time after UEFI took over stewardship of the spec
You might argue that the firmware should simply not do anything at runtime because it is not the firmware s job to do that, and I do understand that and you can certainly boot with acpi=off if you want to and no ACPI code will be executed at runtime. Let me know how that goes.
I m not going to present an opinion on that here, merely say that this provides no supporting evidence for that assertion
This post is part of a series called "Pigeon". If this is the first post
you've found, it'd be worth reading the
intro post first and then looking over
all posts in the series.
The final step to all of this was to tie together all my PHY RF
code, Link layer parsers, and my
background with operating systems
to make this all feel like a normal thing my computer should be doing.
At the end of the day, I want my host system to know how to talk with a
pigeon daemon, so I don t have to reimplement basically everything else.
My ability to use normal tools like curl or ping6 is pretty important
here, so I need to reach for my old friend, the
TUN interface. The
TAP/TUN interface allows the kernel to route ethernet frames (TAP) or ip
packets (TUN) to a userspace program responsible for handling delivery and
reception avoiding the need for a kernelspace driver for something that
can be handled in userland.
wondering if doing this violates FCC Part 97 rules? I wrote up
notes on my test setup
for exactly this question, but the short answer is "no"!
I m nostranger to
playing with TAP/TUN, so this was pretty easy to snap together although this
time I avoided the whole ethernet proxying thing (to side-step lossy
translations, maintaining two sets of mac address tables, and handle proxying
NDP/ARP messages) it was kinda a bad idea last time so I just used TUN
and straight IP for now. While implementing this, I decided I d make a key
assertion about all pigeon networks namely, all pigeon IPv6 networks are a
/64 in size, no more, no less. The reason why I m doing this here is that,
since pigeond does still does need a MAC address for the pigeon layer 2
protocol, we can write our daemon to always use
SLAAC
to set the TUN IP address without any new information.
Which leads us to a bit of an aside, but I have a point, I swear. A few years
ago, my recreational RF adventures have lead me down a path where I decided to
engage with ARIN to solve (once and
for all) the massive headache I was running into with IPv6 numbering (really:
always renumbering) my multi-site radio processing networks. It s a lot
of work to keep running correctly, but it s solved a huge amount of
problems for me.
The only internal thing we really need to outline for this post is that, at
the highest level, my network (paultag.net) is split into an IP plan that
looks roughly like:
64 "sites" per region. A "site" is assigned to a physical or logical location.
/64
1024 subnets per site. A subnet used by directly attached devices.
For this exercise, I used IP space from paultag.net s experimental region
( region 8 ), named side.band (2602:810:6008::/48) to connect my RF lab
( site 1 - 2602:810:6008:400::/54), and my two pigeon-specific subnets,
subnet 0 (2602:810:6008:400::/64) and subnet 1 (2602:810:6008:401::/64)
to my wider network. The first subnet ( subnet 0 ) is a simple ethernet network
to enable my RF-only nodes to communicate with the side.band gateway. The
second subnet ( subnet 1 ) is an RF-only pigeon network local to my lab.
back to radios
With all that set up, I assigned my first two nodes their MAC addresses, and
set up the local RF only network segment. The nodes I brought online were the
following:
Callsign
IP
K3XEC/MN
2602:810:6008:401:8e1f:64ff:fe35:4001
K3XEC/TH
2602:810:6008:401:8e1f:64ff:fe35:4002
testing the pigeon network
And with that, I could begin to test that the host operating systems and RF
links could properly exchange data locally from SDR to SDR. We can use
ping6 to see if a plain-ole ICMPv6 ping round trips between hosts correctly:
$ ping6 2602:810:6008:401:8e1f:64ff:fe35:4001
PING 2602:810:6008:401:8e1f:64ff:fe35:4001 (2602:810:6008:401:8e1f:64ff:fe35:4001) 56 data bytes
64 bytes from 2602:810:6008:401:8e1f:64ff:fe35:4001: icmp_seq=1 ttl=64 time=426 ms
64 bytes from 2602:810:6008:401:8e1f:64ff:fe35:4001: icmp_seq=2 ttl=64 time=397 ms
64 bytes from 2602:810:6008:401:8e1f:64ff:fe35:4001: icmp_seq=3 ttl=64 time=419 ms
64 bytes from 2602:810:6008:401:8e1f:64ff:fe35:4001: icmp_seq=4 ttl=64 time=418 ms
64 bytes from 2602:810:6008:401:8e1f:64ff:fe35:4001: icmp_seq=5 ttl=64 time=436 ms
64 bytes from 2602:810:6008:401:8e1f:64ff:fe35:4001: icmp_seq=6 ttl=64 time=391 ms
64 bytes from 2602:810:6008:401:8e1f:64ff:fe35:4001: icmp_seq=7 ttl=64 time=397 ms
And it does! Latency is horrid (and there s a bunch of tx artifacts that
cause issues for us) but both of those things are problems for later. Let s
see how it handles a TCP connection by firing off a quick cURL across the
Pigeon network:
$ curl http://[2602:810:6008:401:8e1f:64ff:fe35:4001]:8000/testing.txt
The rock dove (Columba livia), also known as the common pigeon or rock pigeon
(but see also Petrophassa), is a member of the bird family Columbidae (doves
and pigeons).
As expected, our remote end here running the server reports the correct peer
IP address, which is another indication (beyond the log messages and blinking
LEDs) that we re routing over our TUN interface.
Serving HTTP on 2602:810:6008:401:8e1f:64ff:fe35:4001 port 8000 (http://[2602:810:6008:401:8e1f:64ff:fe35:4001]:8000/) ...
2602:810:6008:401:8e1f:64ff:fe35:4002 - - [28/May/2026 12:53:21] "GET /testing.txt HTTP/1.1" 200 -
That worked? First shot! Nice! It s pretty slow and seems like we have a
lot of packet loss, but it does, however, beg the question can it nethack?
nethack!
Yes! It can nethack! No clickbait here. The way I went about this one is a bit
anit-cimatic I set up a nethack server (using inetd in this case) on one
of the hosts pigeon0 network interface, and hit that port over RF from
the other:
However, when playing it, it becomes very obvious (as you can likely see) that
there s a fair amount of packet loss (understandable) and probably some packet
collisions taking place.
iperf
Let s try and put a number to exactly how bad the bandwidth and packet loss
is by running iperf between the two pigeon hosts over rf:
$ iperf -c 2602:810:6008:401:8e1f:64ff:fe35:4002
------------------------------------------------------------
Client connecting to 2602:810:6008:401:8e1f:64ff:fe35:4002, TCP port 5001
TCP window size: 16.0 KByte (default)
------------------------------------------------------------
[ 1] local 2602:810:6008:401:: port 58248 connected with 2602:810:6008:401:8e1f:64ff:fe35:4002 port 5001
[ ID] Interval Transfer Bandwidth
[ 1] 0.0000-20.2348 sec 76.8 KBytes 31.1 Kbits/sec
Shockingly, not nearly as bad as I thought it was going to be. Given I ve
spent exactly zero time making this operate to a level that I would call
acceptable, this is a very fucking solid start. I expect I could get that
number up if I spent a few weeks on it it s just not been a priority
at any point yet (and the first time I ve instrumented it, even!).
This ll be good enough to get started. Let s see what else we can pull
off here.
IP multicast to some rtl-sdrs
Back when I designed what I wanted Mode A to
look like, I intentionally picked a signal bandwidth that could be received
by an rtl-sdr so let s put that to use. It may go without saying,
but just to say it the rtl-sdr can not transmit, so this will be capable
of receiving pigeon frames but not sending any in reply.
However, this means I can use a bunch of low-cost computers (raspberry
pi-class), and low-cost SDRs (rtl-sdr) and still receive IP traffic from
transmitting pigeon network stations. This could be a lot of fun for things
like fountain coding a data
stream, or adapting multicast streaming protocols to work over RF links.
Anywho, I swapped my far end to an rtl-sdr (one config file change!), and
figured I d start with some (basic) multicast traffic, transmitting the time
once a second:
If I had more time to burn, I was planning on bridging
APRS traffic
to UDP multicast within a pigeon network subnet. However, since I m already 4
years late on this blog post, I figured this would be enough for now (and you
can imagine that fun project in this space if you so wish!)
I fired up pigeond again (except this time connected to an rtl-sdr),
and was pleasantly surprised to be greeted by some decoded traffic right
off the bat:
Looks great! tcpdump is showing multicast packets show up (as we assumed they
would), on the pigeon0 interface, on the machine connected to an rtl-sdr. Of
course, any replies will get sent to the
bit bucket, but it can definitely
decode things just fine! Very fucking cool.
Well right, ok! Let s go back to two rx/tx radios, and see what we can do with
our newfound network stack over ham radio frequencies let s try to do some
fun (and traditional!) ham radio things with it!
Winlink
Winlink is a ham radio mail relay system for ham radio
operators to send, receive or relay mail over the internet, or RF (usually HF
or VHF/2M). Winlink relays are accessible via whatever transport you can
find most commonly telnet (using the internet), ax.25 (usually 2m VHF)
or VARA HF (unsurprisingly, on HF). I use pat as my
Winlink client it s written in Go, doesn t require windows, and is just
generally nice to work with.
Let s try the easy thing first let s connect by proxying the Winlink server
into the pigeon network using socat (lightly edited to remove date/times)
$ pat connect pigeon
Connecting to WL2K (telnet)...
Connected to [2602:810:6008:401:8e1f:64ff:fe35:4002]:8772 (tcp)
[WL2K-5.0-B2FWIHJM$]
;PQ: 54509561
CMS>
>FC EM OLU6BP5HKMG2 240 205 0
>F> 95
FS Y
Remote accepted OLU6BP5HKMG2
Transmitting [Hello, World] [offset 0]
Hello, World: 100%
FF
>FQ
Disconnected.
$
Lo and behold, shortly after, I got this delightful message to my
email address, relayed in from WINLINK:
The only shame is I won t be able to check in to a winlink
wednesday using this scheme unless I further
proxy this message over AX.25 instead of relaying to Winlink s servers over
telnet (which, to be fair, is definitely also possible I just got lazy when
I glued this one together see note above about being 4 years late on this
post).
But, you know, connecting to a host that is using socat to proxy a
connection to an internet resource is interesting but you know what, fuck it
hang on, dear reader let s bang a hard left turn and just ship this thing
hard and directly connect it to the internet. Let s take our dinky,
home-built PHY and Layer 2 and see if we can wire it directly into the internet
something that, every time I go to think about it, reminds me of
Tim FitzHigham and his crapper.
Crossing the english channel in a bathtub
Ok, ok. I decided to bury the lede a bit here I didn t mention that the
side.band network is currently
BGP announced. Although we
haven t used it this does mean that we re most of the way to sending packets
to the wider internet, and we should be able to just fix a few routing
tables, and see packets begin to flow.
After tweaking the local routing tables (and restarting pigeond for good
measure), I decided to test my newfound connectivity by pinging something over
our new network transport.
ping github
Why don t we start with the world s premier software engineering platform,
operated by one of the largest companies in the world, GitHub! After all,
they have an all knowing (and, apparently, arguably sentiant?) AI on hand to
instantly and automatically fix any stray
reliability issues in the
background, so we should definitely see replies right off the bat:
$ ping6 github.com
ping6: github.com: Address family for hostname not supported
Wait, oh no that can t be right?
After all, it s 2026, and both
Google
and CloudFlare
(in North America) are reporting
over half of all traffic they see is IPv6 and GitHub still doesn t support
IPv6? Definitely not, this is for sure a bug with my code or network.
lets ping something that supports ipv6 instead
That being said, just for completeness sake, since that error is also given
when there s no IPv6 DNS record, let s go ahead and double check with
Hurricane Electric too, you know, just to be sure.
$ ping6 he.net
PING he.net (2001:470:0:503::2)56 data bytes
64 bytes from he.net (2001:470:0:503::2): icmp_seq=1 ttl=53 time=514 ms
64 bytes from he.net (2001:470:0:503::2): icmp_seq=2 ttl=53 time=230 ms
64 bytes from he.net (2001:470:0:503::2): icmp_seq=3 ttl=53 time=248 ms
64 bytes from he.net (2001:470:0:503::2): icmp_seq=4 ttl=53 time=246 ms
64 bytes from he.net (2001:470:0:503::2): icmp_seq=5 ttl=53 time=265 ms
64 bytes from he.net (2001:470:0:503::2): icmp_seq=6 ttl=53 time=240 ms
Well, shit. Right, OK, i ll be damned. 18 years in and GitHub still can t crack
that nut.
cURL works!
Right, anyway, yes, back on track good news! Our uplink is up and routing,
and wait, holy shit! Check it out! pigeon is
exchanging packets with the internet and no one is any the wiser!
Literlaly amazing. Let s try a cURL across the internet now (although no
TLS allowed, so, http only for now):
IRC works, too
Sweeeeet. That all works! Forget HTTP, let s do some other 90 s era
stuff, it s high-time to log into IRC with a quick /connect -notls, and see
what s going on in the #debian-hams channel pleased that I got online
fairly quickly, and was able to even talk to myself!
THE GOPHERSPACE
Naturally, let s keep this train of nostalga running, and give
the 2026 gopherspace a
shot.
I know the kind folks over at tilde.town (hello,
townies!) have a robust gopherspace, so let s give it a dial! Let s try and see
if we can load vilmibm s
slug over gopher:
Yes! I forgot to make this one a video, so no gif. I did wind up having a bit
if trouble with a few gopher clients and IPv6 support I may send some
patches if I can find the time.
So, what s next?
Alright, that s it. I have a few more fun ideas but they re going to have to
wait for another day. Carrying IP is fun and all but kinda not the point behind
pigeon, after all. Rather than trying to make this into a thing , I m planning
on exploring the loose ends first different types of modulation schemes
(like QAM-NUC), implementing LDPC error correction and some layer 2 logic
into the pigeond (like switching traffic, and gain control). I also plan
on spending some time with my (currently, very basic) simulator to better dial
in tradeoffs throughout the stack.
Since, structurally, pigeon is something I feel like I can work with, I m
hoping i ll be able to find the time for some (much smaller!) followup posts
without it taking 4 years this time. If I do, they ll show up under the
pigeon tag and I ll be sure to update this post with
a link below (and the intro post).
I m hoping that this series (which was supposed to be one post) was helpful
to someone out there if it was, feel free to reach out and let me know!
This post is part of a series called "Pigeon". If this is the first post
you've found, it'd be worth reading the
intro post first and then looking over
all posts in the series.
Now that we have a working Layer 1, we have a way to send a block of bits
from one place to anyone who cares to listen to us. This is very welcome
news, but we are now facing a new, different and just as fun question what
shape should that data take?
Need a bit more of a crash course on what "Layer 1" and "Layer 2" mean? No
problem, I wrote up short summary here to
help.
Given our incredibly limited functionality of our nodes, we could definitely
skip all this work and just stuff an IP packet into the link; but I decided
to not since I am (eventually) interested in adding some sort of
spanning tree-like
protocol to implement network
switching so not all nodes
need to communicate directly with all other nodes but that day is not today.
Given i m going to stub most of that out, let s take a look at what some
similar Layer 2 protocols use things like Ethernet or WiFi frames. Both
contain structured information regarding the transmitter, desired recipient,
type of data, and the higher-level data itself (such as IP packets). As a
result of attempting to learn from others, the Pigeon Layer 2 (called, simply,
link ) is also split into a fixed-length header, followed by the contents
described by the header.
The header is a fixed-length (23 byte) structure, which contains the source
MAC address (src mac), destination MAC address (dst mac), the ITU
coordinated ham radio callsign of the control operator of this message
(callsign), the type of payload to follow (type; defined below), and
the length of the data to follow the header (length as a 16 bit big-endian
unsigned integer).
The type field indicates how the payload is to be interpreted currently
I ve only defined 3 possible payload types so far:
Keen observers will perhaps infer that there used to be an Ipv4 type at
0x03 which is true however, i ve since removed it since i ve never once
used it and the codepath was more trouble than it was worth. As is my wont,
I ve optend to just lean into Ipv6-only IP transport it s easy enough to
shim ipv4 in, if someone REALLY wanted to using something like 64:ff9b:1::/48
and a bit of code in the transmitter/receiver (or even using something like
jool and unbound s
dns64-prefix
at the router). I don t think I ll bring it back, but just in case I have
to for some reason in the future, it s there.
Additionally, friends of the pod may also recognize that this structure is
basically the exact same structure as what I had in PACKRAT,
which, is also true. I started this project off maintaining interoperability in
the Layer 2 for pigeon and packrat, but at some point just gave up on it during
one of the many cleanups. I m hopeful I can maintain compatibility going
forward, and that won t have to muck with this header too much more. We ll see
what happens once I start to push the bounds of what is possible with pigeon.
Hopefully it feels like carrying IP data inside this frame to be a pretty
self-explanatory exercise the 0th byte of the payload is the 0th byte of
an IPv6 header (followed by all the usual stuff, like UDP or TCP header(s) and
any carried data, just like you d find anywhere else.
Pigeon s calabration protocol
My Debian contributions this month were all sponsored by Freexian.
You can also support my work directly via Liberapay or GitHub Sponsors.
Personal note
This month, my Dad unexpectedly passed away after a short illness. As a result I obviously got less work done than usual, and I still have a lot to take care of (since I m the executor of his will, as well as helping with funeral arrangements) while grieving and generally having less focus and energy. Having routine work to do is one of the ways I cope with this sort of thing, but all the same, I hope people will bear with me and maybe remind me if I seem to be dropping the ball on something you especially need.
LLM vote
[Content note: strong opinions.]
I voted in General Resolution: LLM usage in Debian. My vote was pretty much the opposite of what ended up winning, so I m quite disappointed. My personal opinion is that LLMs are cognitive hazards to their users that impose ecological costs far out of proportion to their utility at a time when the world absolutely cannot afford them. When the impossible economics of the large commercial models are finally allowed to catch up with reality, I expect there to be significant macroeconomic consequences, and that people who have become dependent on them will have problems; and who knows what the copyright situation on their output really is. I m not convinced that local models are better enough on these axes to be worth the costs.
Debian s direct contribution to all that will be negligible on a global scale, and even the most radical proposals in the GR didn t expect that we could do much about upstreams that have gone all-in on LLMs. Even so, I d hoped that my fellow developers might be more willing to lean on our position in the free software ecosystem to make at least a moderately radical statement. Instead, we ve at best presented an undistinguished fence-sitting position to the world, and further entrenched the idea that humans can reliably do a good job of reviewing the output of tools that are designed to produce output plausible to humans. I certainly don t trust my own code review skills that far.
Since I ve never voluntarily used an LLM (not counting LLMs being foisted on me by things like search results, support chatbots, or incoming pull requests, regardless of whether I asked for them), and don t intend to for the foreseeable future, I doubt this will change much for me in terms of the way I work. The winning option is a very weak one that imposes no new requirements on developers, which means that it also does nothing to stop me continuing to reject LLM-generated material from Debian bug reports and merge requests in my areas of responsibility. I know this probably won t do much to satisfy people who have decided that Debian is slop now, but it s the best I can do.
OpenSSH
I finally landed the GSS-API key exchange package split in our OpenSSH packaging. Here s the NEWS entry:
I fixed a flaky autopkgtest.
I upgraded from 10.4p1 to 10.5p1, which was a good test of keeping openssh and the new openssh-gssapi source package in sync.
PuTTY
I upgraded from 0.84 to 0.85.
Python packaging
New upstream versions:
The version treadmill continues: we ve just finished dropping Python 3.13 as a supported version, so now we ve started working on enabling Python 3.15 as a supported version. Maximiliano Curia has been very helpfully driving this. I didn t get as much done here as I d have liked (see the top of this post), but I fixed a couple of packages:
The AVIF image format gets more and more popular in the web dev community, so I needed to teach XFCE4's thunar (file manager) and Ristretto (image viewer) to thumbnail these.
Luckily that is not too hard:
Debian Trixie separates its gdk-pixbuf libraries slightly differently than previous versions. That's why it is not "automatically there". Ensure you have the libavif-gdk-pixbuf plugin and the tumbler service (which XFCE uses to process thumbnails):
Thunar has likely tried (and failed) to load your AVIF files before you installed the package, it will have saved a blank or "broken image" placeholder in a thumbnail cache directory. It will not attempt to regenerate them unless you clear this cache:
# Clear the thumbnail cache rm-rf ~/.cache/thumbnails/*
# Force-quit thunar and the tumblerd background service thunar -q pkill tumblerd
Tumbled will restart on its own when it is needed. When you open thunar again and navigate to your image directory ... your AVIF images will now generate thumbnails automatically like the other image format did already.
I am a heavy user of sidenotes:1 they keep optional content next to the
text instead of sending the reader to the bottom of the page and back. Tufte
CSS renders them without JavaScript but only accepts inline content. CSS
anchor positioning, now supported by recent browsers,2 is an
elegant alternative. Sidenotes can hold several blocks, still without
JavaScript, and fall back below the paragraph referencing them on narrow
viewports and older browsers.
In 2023, Eric Meyer demonstrated this technique in Nuclear Anchored
Sidenotes. The main improvement over other solutions is that the notes can
sit anywhere in the HTML document. You can place them after the paragraph
referencing them, as regular block elements for text browsers, screen readers,
feed readers, and reader mode to render them properly:
Rendering in Lynx, a text browser
When the viewport is too narrow or the browser does not support CSS anchor
positioning, you can style them so the reader can skip them or glance at them
without losing their position in the text:
Rendering below the paragraph on a narrow viewport
Once the viewport is large enough, they appear in the margin, at the same
vertical position as the matching reference mark, unless they would collide with
a previous sidenote, as in the example below:3
Rendering in the margin on a large viewport
The gist of CSS anchoring is to position an element relative to another
element the anchor. For the sidenotes, the anchor is the reference mark. I use
the following markup, with a data attribute to specify the anchor name:
The matching note is an <aside> element carrying the same data attribute for
the anchor name. We put it after the paragraph holding the reference mark:
<asiderole="note"id="sidenote-YYY"data-anchor="--lf-sn-YYY"><sup>1</sup><p>A first paragraph.</p><p>A second paragraph.</p></aside>
On a narrow viewport or when the browser is too old for CSS anchoring, we style
the sidenote, which stays below its paragraph, with a muted color:
aside[role="note"]margin-block:1rlh;color:#444;
On a wide viewport and when the browser is recent enough, we move the sidenote
to the right margin:
attr() extracts the anchor name for the reference mark from the data-anchor
attribute. It returns a string, unless we specify a CSS unit or a type, like
here: the browser parses the data attribute as a custom
identifier, which anchor-name validates as a dashed
identifier, a custom identifier starting with two
dashes.4
The note itself is absolutely positioned past the right edge of the main block.
It selects the matching reference mark as its anchor with position-anchor set
to the value of the data-anchor attribute. Each note is also an anchor named
--lf-sidenote. We use it to keep the next note from colliding with this one.
The anchor() CSS function lets us position the note s top
edge relative to its anchor: anchor(top) aligns the top edge of the note with
the top edge of the reference mark. It can also take another anchor as a
parameter: anchor(--lf-sidenote bottom) would align the top edge of the note
with the bottom edge of the closest preceding anchor named --lf-sidenote so
the previous note.5 Like attr(), anchor() accepts a fallback
value as its second parameter and use it when the named anchor does not exist.
The top property handles three cases, illustrated in the following diagram:
The three cases for the vertical position of a note
The first note s top edge aligns with the top edge of its reference mark: as
there is no previous note, anchor(--lf-sidenote bottom, -1rlh) + 1rlh
resolves to 0 and max() returns anchor(top).
When the reference mark of a later note sits above the bottom of the previous
note, plus some vertical space, the note goes below the previous one to avoid
a collision. max() returns anchor(--lf-sidenote bottom) + 1rlh.
Otherwise, the note s top edge aligns with the reference mark s top edge, as
max() returns anchor(top).
Have a look at the complete stylesheet, which also adapts the
reference mark to the location of the note: a arrow when the note sits below
the paragraph, a arrow when it moves to the margin. Gwern s Sidenotes In
Web Design lists more implementations and their trade-offs.
Some bloggers aim to write a post in 30 minutes. I planned to publish
three web-related articles this weekend. Instead, I spent an inordinate amount
of time elsewhere: about 15 commits on the build system, a pull request to
update CSS highlighting for nested selectors in Pygments, and a
small correction to MDN s article on the anchor() CSS function. The
SVG illustration took a bit less than an hour and the article itself a handful
of hours. The attr() function came in after I thought inline style looks
ugly, isn t there a better way? But, hey, I still think this is worth it!
My PhD advisor told me this is unwise.
The first bits of anchor positioning are supported from Chrome 125 (May 2024), Firefox 147 (January 2026), and Safari 26 (September 2025).
Before Safari 26.5, sidenotes may collide due to a bug in how dependency
chains are handled. You can detect this situation with some JavaScript.
It is, however, not needed in the solution described here as we depend on a
more recent feature.
If you noticed the runt in the first note, I share your pain and lament that
Firefox does not implement text-wrap: pretty.
Typed attr() is supported from Chrome 133 (February 2025),
Firefox 155 (September 2026), and Safari 27 (September 2026). Check Una
Kravets article for details. To support more
browsers, you can inline the anchor name and the position anchor directly in
the HTML:
The exact rule for the target anchor element is more complex: if an
ancestor of [the note] satisfies the following conditions, return the
nearest such element to [the note]. Otherwise, return the last element in
tree order that satisfies the conditions. One of these conditions is that
[the candidate] is an acceptable anchor element for [the note], which
requires that [the candidate] is laid out strictly before [the note],
where the relevant clause is that [the candidate] is either not absolutely
positioned or occurs earlier in the flat tree order than [the note].
I have just tried CoMaps, a free mapping program released under the Apache license [1]. I have tried it on Android on a Pixel 6a but it also runs on Linux so I ll try it on a PinePhone or similar at some convenient time. On Android it is in the F-Droid repository among others and for Linux there s a Flatpak package.
The data it uses is from Open Street Map project [2] which has extensive and accurate coverage of every place I ve looked at (Australia and a few other first-world countries). The first thing it does after being installed is start downloading the world data set from Open Street Map and prompt to download the data for the detected region (Melbourne in my case).
The UI is decent and allows most of the features that I am used to using in Google Maps. The quality of directions seems good, I ve only tested it with one journey so far which was a 50 minute drive across the city and it gave a set of directions that Google Maps often gives.
It gives spoken directions which is an important feature but sometimes the way the directions are presented is confusing. When turning off a freeway it didn t give a spoken direction to do that, it gave a direction to turn right which was AFTER leaving the freeway, fortunately the map was clearly displayed.
In terms of use practices of this program the main difference I recommend is checking which off ramp to use from a freeway before entering the freeway. With Google Maps you can rely on it giving clear directions in that case.
I recommend this program without reservation. It can do everything that Google Maps does apart from detecting traffic jams because there s no way of detecting traffic without spying on users. It is designed to preserve user privacy and works well in that regard.
This August, I accomplished what I wanted for many years: I deleted the last cgo
dependency in Debian Code Search! This was made possible by Go s recently
introduced SIMD support, because now we can implement the TurboPFor integer
compression format as efficiently more efficiently, in fact, by using the
newer AVX512 instruction set! as the reference implementation.
Background: Why does DCS need a fast Integer Codec?
Debian Code Search (DCS) is a search engine that allows searching all the Open
Source source code within Debian, with either literal search expressions or
regular expression search queries.
A search engine uses an inverted index: a map from term to documents containing
the term. Each document is typically represented most efficiently by using an
id, so the index consists of many lists of document ids.
When searching, it is important to quickly decode these lists to answer the
search query. However, there is a point of diminishing returns where the
decoding speed, even though it can still be measurably improved quite a bit, no
longer influences the overall query duration.
From 2012 (its inception) to 2019, Debian Code Search used to use a small index
format, and queries were fast because the index was kept entirely in RAM. In
2019, I implemented the new index
format, which adds an
on-disk positional index. For literal queries (78.2% of DCS queries), querying
the positional index on disk is faster than querying the non-positional index in
RAM.
The efficient encoding of the TurboPFor format makes it possible to fit such an
index on a mid-sized Hetzner server, which I rent with two 1 TB SSD disks. The
optimized decoder of the C TurboPFor library is what made decoding fast at query
time.
If you want to dive deeper into the algorithm, see this blog post from February
2019:
Use a C library via cgo so gcc or clang compiles
SIMD code. Debian Code Search used to use the
powturbo/TurboPFor
C library via cgo for the last 7 years.
The C TurboPFor library has served us well, but Debian Code Search was always
intended to be a project using Go, so I would prefer it if I did not have any C
code in the project.
Go 1.26 (released in February 2026) introduced the simd/archsimd package:
Go 1.26 introduces a new experimental simd/archsimd
package, which can be enabled by setting
the environment variable GOEXPERIMENT=simd at build time. This package
provides access to architecture-specific SIMD operations. It is currently
available on the amd64 architecture and supports 128-bit, 256-bit, and
512-bit vector types, such as Int8x16 and Float64x8, with operations such
as Int8x16.Add. The API is not yet considered stable.
Go 1.26 Release Notes
For my 2019 TurboPFor analysis, I implemented goturbopfor, a native Go
teaching decoder (without any SIMD),
because I find Go code easier to follow than C code, especially optimized C
code. My implementation was intentionally not optimized so that the code was
easier to study.
The TurboPFor format/algorithm has a vector-optimized part: bitpacking comes in
a scalar variant (bitunpack32) and a vector variant
(bitunpack256v32),
where the vector variant is used for full blocks (256 values) and the scalar
variant is used for remainder blocks (< 256 values).
When Go 1.26 was released, I used Claude Code to explore whether my native Go
decoder s bitunpack256v32 function (for the vertical vector layout) could be
implemented using Go SIMD, and the answer was yes, it was possible and it was
faster than without SIMD, but not quite at the level of C TurboPFor. If you let
Claude Code try for long enough, it eventually finds enough optimizations (about
10) to match C performance.
I don t want to vibe-code Debian Code Search, though, so I figured I would find
some time to review the SIMD code at some point and see if I could implement
something similar myself.
Before I found enough time and motivation to complete said review, I discovered
that to not regress real-life query performance by more than 10 to 100
milliseconds (which seems acceptable), I don t actually need to add SIMD code to
my teaching decoder at all; it would be sufficient to reduce allocations in my
teaching decoder and specialize it per bit width.
Encouraged by the possibility of using the optimized native Go decoder in Debian
Code Search, I explored whether I could also implement a native Go encoder so
that I could get rid of the C TurboPFor dependency entirely. The answer is yes,
it is doable in a few days, and it isn t even that much slower: Go is at 76% of
C, see Debian/dcs commit
e920dc7.
The goal I set myself at that point was to see if I could learn enough SIMD to
optimize the native Go encoder such that its performance would match how DCS
uses C TurboPFor (via cgo).
Beating C TurboPFor was possible in 2-3 commits (SIMD and bit width
specialization). To my surprise, Claude Fable 5 pointed out that the encoder s
block scanning could be done more efficiently using a technique called
positional popcount, and that is another 2x speed-up!
To be clear: I am not saying the Go compiler beats C here. Certainly, the C
compiler can also produce fast AVX512 code and can be used to implement
positional popcount. When comparing apples to apples, i.e. backporting the
AVX512 kernels and positional popcount technique to C TurboPFor, Go benchmarks a
little slower at 1.4x C.
This spectacular result (much faster than what DCS had before) got me curious
how far I could push the decoder with SIMD after all. I ended up
matching/exceeding the cgo version here, too!
The rest of this article explains a few classes of optimizations I encountered
along the way.
Starting Point
When I wrote my goturbopfor teaching
decoder, I named its functions to
match the upstream C TurboPFor library, but now I want to get away from names
like p4ndec256v32 they make sense from the TurboPFor perspective, but for
Debian Code Search, we can use cleaner names.
Before writing any code, I audited how DCS uses integer compression /
decompression.
API design: BlockEncoder, BlockDecoder and streaming
In Debian Code Search, we have the following usage patterns:
Partial Indexing: When a new package (or package version) enters Debian,
all of its (text) files are indexed. If the hello-2.12.3-1
package (hypothetically) contained
only hello.c with printf("hello!\n");, we would assign document ID 1 to
hello.c and store in the partial index that trigrams pri, rin, int,
ntf, etc. are all found in doc 1 (hello.c).
Full Index Merging: The many thousands of partial index files (for each
Debian package) are combined into a small handful of large index files: When
searching, it would be expensive to consult thousands of indexes. To merge
multiple partial index files into one larger index (which can then be
efficiently queried), we need to re-encode the partial index files: what used
to be document ID 1 in the partial index might be document ID 2531 in the
full index.
Querying (searching): When users enter search queries, these queries need
to be answered as quickly as possible. The relevant entries in the full
indexes are decoded (in parallel).
For reading the index, we do keep the decoded uint32s fully in memory, so we
only need DecodeN(input []byte, output []uint32) (read int), a function that
reads len(output) values (uint32) from input and returns how many bytes it
consumed.
For writing the index (both in partial indexing, and when merging), keeping the
entire index in memory is prohibitively expensive, so we need a streaming API,
for decoding and for encoding.
Ultimately, I converged on the following API:
packagepforenctypeBlockEncoderstruct// scratch buffers can go here// EncodeBlock encodes len(vals)<=256 uint32s into dest (one TurboPFor block).func(*BlockEncoder)EncodeBlock(dest[]byte,vals[]uint32)[]byte// EncodeN calls EncodeBlock in a loop.func(*BlockEncoder)EncodeN(dest[]byte,vals[]uint32)[]bytetypeStreamEncoderstructbeBlockEncodervals[256]uint32// scratch buffers// if full, you need to call [EncodeBlock]func(*StreamEncoder)Add(valuint32)(fullbool)// EncodeBlock must be called after all data was [Add]ed.//
// Write the returned buffer to file or send it over the network;// it is only valid until the next [EncodeBlock] call.func(*StreamEncoder)EncodeBlock()[]byteifse.n==0returnnil// turn an extra EncodeBlock into a no-op//
This API (the decoder works similarly) allows us to process data in TurboPFor
format without any memory allocations. The types are not safe for concurrent use
by multiple goroutines. The zero value is ready to be used. For the streaming
API, the result only stays valid until the next call.
Initial Implementation
Before we can optimize anything, we need a working decoder and encoder. The
decoder already exists: my goturbopfor teaching decoder. Next up, I needed an
encoder.
Writing a TurboPFor encoder has a delightfully simple starting point: You can
encode all values at bit width 32, in little endian, at which point you only
need to add a one-byte TurboPFor block header every 256 values and you re done:
Of course, this is a terribly inefficient compressor, so after the first commit,
the real work starts: implement each block type until the compression matches
the original C TurboPFor implementation (same output file size), or in other
words: do the reverse of the decoder.
The TurboPFor bitpacking block type (bitpacking implementation
commit)
encodes a bit stream of variable bit width (where the bit width is in range
0 bitWidth 32) in little
endian byte order. By scanning all
values and choosing the smallest bit width that allows representing all
values, this technique saves disk space (compresses).
The bitpacking with exceptions block type (bitpacking with exceptions
implementation
commit)
determines two bit widths: one for values, the other bit width for encoding
exceptions. This allows choosing a lower bit width (that does not cover all
values) compared to the bitpacking block type. A bitmap encodes whether a
value has an exception or not.
The bitpacking with VB exceptions block type (bitpacking with VB
exceptions implementation
commit)
is a variant which does not use an exception bitmap and encodes exceptions
using a variable byte integer encoding. This is more efficient when there are
few exceptions (less than 20) or the exceptions are very different in bit
width compared to the other values.
Lastly, the constant block type (constant implementation
commit)
stores just one value on disk. This is useful for all-zero or all-one blocks,
for example.
I found it interesting to realize that the main work of the encoder is to scan
the input values and choose the optimal block type, whereas the actual encoding
itself is cheap in comparison.
At this point, we can look at
performance
and see that the Go encoder is at 76% of the C encoder.
In all honesty, I could have probably stopped here, but now that the milestone
of a viable replacement was reached, I got curious to see how far it would be
possible to push the encoder (how much work to reach C speeds?) and afterwards,
the decoder, too.
Setup
The microarchitecture level: set GOAMD64
The microarchitecture of a CPU determines which instructions it provides, and
that includes not just SIMD instruction sets (like AVX2), but also other useful
instructions like LZCNT (Leading Zero Count), which can be used to implement
math/bits.Len32 more efficiently, which
the TurboPFor encoder needs to call on every input value to determine the ideal
bit width.
Let s walk through how to set the microarchitecture level when using Go on
64-bit x86 (x86-64).
Go uses the GOARCH environment
variable to configure the target
compilation architecture, and I am using the value amd64 to select 64-bit x86
(AVX2 and AVX512 are instruction sets found on x86-64 CPUs). With
GOARCH=amd64, the architecture-specific variable
GOAMD64 configures the
microarchitecture level for which to compile and Go 1.18 introduced these 4
different levels:
GOAMD64=v1 (default): The baseline.
Exclusively generates instructions that all 64-bit x86 processors can execute.
GOAMD64=v2: all v1 instructions,
plus CMPXCHG16B, LAHF, SAHF, POPCNT, SSE3, SSE4.1, SSE4.2, SSSE3.
GOAMD64=v3: all v2 instructions,
plus AVX, AVX2, BMI1, BMI2, F16C, FMA, LZCNT, MOVBE, OSXSAVE.
GOAMD64=v4: all v3 instructions,
plus AVX512F, AVX512BW, AVX512CD, AVX512DQ, AVX512VL.
In 2026, I generally recommend compiling with GOAMD64=v3 so that functions
like bits.OnesCount8 are
compiled into intrinsics
(POPCNT)
instead of using a lookup table.
For Intel CPUs, setting GOAMD64=v3 means your programs will only start on
Haswell CPUs (2013) or newer; for AMD CPUs that means Zen 1 (2017) or newer.
In this specific case (DCS), I am even compiling with GOAMD64=v4. The v4
microarchitecture level requires AVX512, which means AMD Zen 4, Zen 5 or newer
(Intel s story is complicated). Luckily, both my main development PC (Zen 5)
and the Debian Code Search server (Zen 4) are recent enough. Setting
GOAMD64=v4 has little effect on Go 1.27 itself: the only change is that maps
use one less instruction (VPBROADCASTB instead of PSHUFB). But compiling
with GOAMD64=v4 allows us to move one more feature check from runtime to
compile time, see SIMD build tags.
It makes sense to set the microarchitecture level in your benchmark setup so
that you don t measure the slow fallback implementations. I use export GOAMD64=v4 in my Makefile.
Benchmarking setup
Go s built-in testing package contains support for
benchmarks which are written in
functions of the form func BenchmarkXxx(b *testing.B). The simplest way to run
such benchmarks is go test -bench=., but I ended up configuring a few
convenience make targets, which write results to bench.txt and compare
against baseline.txt (the previous commit s results, usually), using the very
useful benchstat tool.
GOTEST=go test# -count=6 gives p 0.002 in benchstat:
# https://pkg.go.dev/golang.org/x/perf/cmd/benchstat
BENCHFLAGS=-run=^$$ -bench=. -benchtime=200000x -count=6# use taskset -c1 to always pin to the same single core,
# avoiding accidental scheduling on different cores on
# mixed-core CPUs like the Ryzen 9 9950X3D.
TASKSET=taskset -c 1BENCH=$(TASKSET)$(GOTEST)$(BENCHFLAGS).PHONY: all test bench bench-baseline bench-relative
all: test
bench: test
$(BENCH) tee bench.txt
# Compares compression ratio between C and Go implementation
benchstat -col /impl -row '/n /vals' -filter '-/impl:go-stream .unit:(encoded-bytes)' bench.txt
# Compares performance between C (cgo) and Go implementation
benchstat -col /impl -row '/n /vals' -filter '.unit:(Mval/s)' bench.txt
bench-baseline: test
$(BENCH) tee baseline.txt
bench-relative: test
$(BENCH) tee bench.txt
benchstat -filter '-/impl:go-stream .unit:(encoded-bytes)' baseline.txt bench.txt
benchstat -filter '/impl:go .unit:(Mval/s)' baseline.txt bench.txt
The encoded-bytes and Mval/s units are custom metrics I am reporting from
the various sub-benchmarks, which are arranged
such that I can filter / report them with benchstat.
The main encoder (and decoder) benchmarks compare 3 different implementations
(cgo, Go, Go with the StreamEncoder API) with a number of benchmark
cases
that are designed to cover the different block types and contain a similar mix
of values as what we see in Debian Code Search:
// reportMetrics adds Mval/s and encoded-bytes metrics to all benchmarks.funcreportMetrics(b*testing.B,nint,nencodedint)b.ReportMetric(float64(nencoded),"encoded-bytes")b.ReportMetric(float64(b.N*n)/1e6/b.Elapsed().Seconds(),"Mval/s")// BenchmarkEncode/n=<N>/vals=<testcase>/impl=<c go go-stream>//
// e.g. BenchmarkEncode/n=2048/vals=one-constant/impl=go-streamfuncBenchmarkEncode(b*testing.B)for_,tc:=rangeallBenchCases()n:=len(tc.vals)b.Run(fmt.Sprintf("n=%d/vals=%s",n,tc.name),func(b*testing.B)b.Run("impl=c",func(b*testing.B)b.ReportAllocs()varencoded[]bytebuf:=make([]byte,turbopfor.EncodingSize(n))forb.Loop()encoded=turbopfor.P4nenc256v32Buf(buf,tc.vals)reportMetrics(b,n,len(encoded)) )b.Run("impl=go",func(b*testing.B)b.ReportAllocs()varbeBlockEncodervarencoded[]bytebuf:=make([]byte,0,turbopfor.EncodingSize(n))forb.Loop()encoded=be.EncodeN(buf,tc.vals)reportMetrics(b,n,len(encoded)) )b.Run("impl=go-stream",func(b*testing.B)b.ReportAllocs()varseStreamEncodervarencodedintforb.Loop()encoded=0for_,val:=rangetc.valsifse.Add(val)encoded+=len(se.EncodeBlock())encoded+=len(se.EncodeBlock())reportMetrics(b,n,encoded) ) )
CPU counters: perf
Go has included excellent performance tooling for many years, see the
Profiling Go Programs blog post (2011) for an
example of how to use pprof, a sampling profiler. This profiler can help track
down which part of a program runs slow, or where memory allocations happen.
Once you identified the slow part of a program, how do you know why it s slow?
To learn more about the specific bottlenecks your program encounters, you can
consult your CPU s hardware performance
counters. For
example, you could check the branch
predictor counters to see if
your program is slow due to a high number of branch mispredicts.
On Linux, the perf tool is the best way to access the CPU hardware performance
counters. A good starting point for working with perf is the documentation on
Top-down analysis with the perf
tool , which describes the
optimization method that Intel established.
In my Makefile, I set up two perf targets:
# GOTEST and TASKSET like shown in the earlier benchmarking setup section:
GOTEST=go test -pgo=encode.cpuprof
TASKSET=taskset -c 1PERFBENCHFLAGS=-test.bench='Encode/n=2048/vals=debian-mix/impl=go$$' -test.benchtime=200000x
# Use perf(1) to capture AMD IBS (the equivalent to Intel PEBS)
# PipelineL1 is roughly equivalent to Intel TopdownL1
perf:$(GOTEST) -c
$(TASKSET) perf stat -M PipelineL1 ./pforenc.test -test.run=^$$$(PERFBENCHFLAGS) sudo perf record -F 4999 -e ibs_op// --call-graph fp ./pforenc.test -test.run=^$$$(PERFBENCHFLAGS) sudo chmod 644 perf.data
# 488281 iterations 2048 values = 1.000e9 values, so counter/1e9 = per value.
perf-per-value:$(GOTEST) -c
$(TASKSET) perf stat -x, -e cycles:u,instructions:u,branches:u,branch-misses:u ./pforenc.test -test.run=^$$ -test.bench='Encode/n=2048/vals=debian-mix/impl=go$$' -test.benchtime=488281x 2>&1 >/dev/null awk -F, ' printf "%-16s %6.2f /val\n", $$3, $$1/1e9 '
The perf-per-value numbers are high level numbers that indicate how much work
the implementation is doing. Reducing the number usually increases speed.
To see the counters for each instruction (and source code lines), I use make perf, followed by perf report. A quick shortcut is perf annotate, which
directly shows the hottest function.
Optimizations (scalar)
Let s first see how far we can get without reaching for SIMD instructions.
(The examples are not necessarily in commit order, but cherry-picked for clarity.)
Profile-Guided Optimization (PGO)
PGO stands for Profile-Guided Optimization and is a feature that Go introduced
as a preview in Go 1.20 (released in February 2023) and shipped as ready for
general production use in Go 1.21 (released in August
2023).
The idea is to capture a CPU profile that records where your program spends most
of its CPU time, which you then provide to the Go compiler to give it more data
to make better decisions.
Most importantly, this way the Go compiler can inline functions much more
aggressively than its usual heuristics allow,
which does have a measurably positive effect in my series of optimization
commits. Another optimization that a PGO profile allows the compiler to do is
conditional devirtualization but
our TurboPFor code does not use any interfaces.
My strategy is to enable PGO before doing any other optimizations, so that we
have the full inlining budget available that PGO gives us, and can measure the
effect of other commits clearly.
Surprisingly, turning on PGO actually decreases our
performance
(-13% geomean), but a closer investigation reveals that we just got unlucky. Let
me explain.
Aside from inlining and conditional devirtualization, PGO also influences
alignment: The Go compiler sets PCALIGNMAX(64, 31) on the first block of a
loop (the loop body ) for all loops in hot functions (per the PGO profile),
i.e. Go will insert up to 31 bytes of padding to make the block land on a
64-byte boundary. Documentation like AMD s Software Optimization Guide for the
AMD Zen5 Microarchitecture (2024,
#58455) explicitly recommends aligning hot loops that way:
[ ] for hot loops, some further knowledge of trade-offs can be
helpful. Because the processor can read an aligned 64-byte fetch block every
cycle, it is suggested to either align the start of the loop to the beginning
of a 64-byte cache line [ ]
Indeed, when compiling with -gcflags=all=-d=alignhot=0 to disable the
alignment, performance remains as good as without PGO. How can the padding hurt
more than help? The answer is: It s not the padding itself! It s a side-effect
of the padding moving instructions to different addresses.
In the unlucky arrangement, a macro-fused CMPQ+JGE instruction pair now ends
up exactly on a 32-byte boundary. However, the Go compiler ensures fused
branch sequences must never cross or end at a 32-byte boundary to fix Intel
erratum
SKX102
(discussion: Go issue #35881) by
inserting NOPs.
This NOP padding, unlike the loop alignment padding, is not free; these extra
instructions slow down our otherwise dispatch-bound loops.
Because the commits after the PGO enabling commit change the code, this unlucky
situation is avoided for the rest of the optimization series (by chance).
Reducing memory allocations
Memory allocations are quite expensive, at least in comparison to
encoding/decoding integers, so I followed my usual strategy of first reducing
memory allocations as much as possible.
In my goturbopfor teaching decoder, whenever the code needed a scratch buffer,
it would allocate it right then and there with make():
// p4dec32 decodes one block of TurboPFor-encoded 32 bit intsfunc(d*decoder)p4dec32(input[]byte,output[]uint32)(readint)// switchblockTypecaseblockBitpackingExceptions:bx,input:=input[0],input[1:]n:=len(output)exmap:=inputnex:=0// number of exceptionsfori:=0;i<n;i++ifexmap[i/8]&(1<<uint(i%8))!=0nex++input=input[(n+7)/8:]exceptions:=make([]uint32,nex)input=input[bitunpack32(input,exceptions,bx):]input=input[d.bitunpack(input,output,b):]fori:=0;i<n;i++ifexmap[i/8]&(1<<uint(i%8))!=0output[i]+=exceptions[0]<<bexceptions=exceptions[1:]returnbefore-len(input)
The Go compiler can turn make(T, n) calls into stack allocations, if n is
known at compile-time. But, in this case nex is not known at compile-time. We
can verify that Go calls into the runtime (runtime.makeslice) by dumping the
object code (assembly) with source annotated (-S):
An easy speed-up was to avoid allocations through
reuse
(in goturbopfor). In the DCS pfordec package (with the improved
API design), I ended up with a vals [256]uint32 field in the StreamDecoder
type, which brings us from 773 Mval/s to 858 Mval/s on the debian-mix:
Aside from the speed-up, avoiding memory allocations is generally nice in
benchmarks because it removes the garbage collector from the equation and makes
it less likely that your benchmarks get other processes OOM-killed on the same
machine.
Generics for bit width specialization
In general, we want to make it easy for the compiler to understand as much as
possible about our algorithm. Consider this bitpack implementation:
Let s think through what determines the iterations and control flow this
function uses:
The number of input values (vals), but not their actual value.
The bit width to pack into (bitWidth).
With a bit of careful rearrangement, we can provide the compiler with both, a
fixed number of input values (say, 32), and a bit width, both known at compile
time. Why is this worthwhile? Because we can manually unroll the loop, let the
compiler eliminate much of the repetition and get much faster compiled code as a
result!
Let s first fix the number of input values to 32 and rewrite the loop to
calculate the position offsets within dest instead of changing dest on each
value (with AppendUint32):
funcbitpack32Unrolled(dest[]byte,vals*[32]uint32,bitWidthint)// only one bounds check for 32 valuesdest=dest[:4*bitWidth:4*bitWidth]mask:=uint32(1<<bitWidth-1)varaccuint64varhave,posint// Manually unrolled loop starts here.// Each iteration is identical except for the vals[x] index.acc =uint64(vals[0]&mask)<<havehave+=bitWidthifhave>=32binary.LittleEndian.PutUint32(dest[pos:pos+4],uint32(acc))pos+=4acc>>=32have-=32// vals[1] .. vals[30] elided for brevity// Each loop iteration is 8 lines of Go code, so for 32 input values,// bitpack32Unrolled contains 8*32 = 256 lines of code.acc =uint64(vals[31]&mask)<<havehave+=bitWidthifhave>=32binary.LittleEndian.PutUint32(dest[pos:pos+4],uint32(acc))pos+=4acc>>=32have-=32// have == 0; for all bitWidths
Next, we want to specialize not just for 32 input values, but also for each of
the 32 bit widths.
Can we do better than hand-copying bitpack32Unrolled 32 times (= 8192 lines of Go code)?
Yes, we can use Go generics to help us with the code generation!
In Go, array types like [4]byte (not
slices like []byte!) contain the length of the array as part of their type,
meaning [1]byte (an array of length 1) is a different type than [2]byte.
Instead of passing the bit width as a function parameter, we can declare 32
different types (one for each bit width) and recover the bit width (at compile
time!) from the type system:
typebitWidthTinterface[1]byte[2]byte[3]byte[4]byte[5]byte[6]byte[7]byte[8]byte[9]byte[10]byte[11]byte[12]byte[13]byte[14]byte[15]byte[16]byte[17]byte[18]byte[19]byte[20]byte[21]byte[22]byte[23]byte[24]byte[25]byte[26]byte[27]byte[28]byte[29]byte[30]byte[31]byte[32]bytefuncbitpack32Unrolled[TbitWidthT](dest[]byte,vals*[32]uint32)varzeroTbitWidth:=len(zero)// known at compile timedest=dest[:4*bitWidth:4*bitWidth]// make cap known at compile timemask:=uint32(1<<bitWidth-1)varaccuint64varhave,posint// Manually unrolled loop starts here.// Each iteration is identical except for the vals[x] index.acc =uint64(vals[0]&mask)<<havehave+=bitWidthifhave>=32binary.LittleEndian.PutUint32(dest[pos:pos+4],uint32(acc))pos+=4acc>>=32have-=32// vals[1] .. vals[31] elided for brevity
When we instantiate bitpack32Unrolled[bitWidthT] with all 32 different types
([1]byte, [2]byte, , [32]byte), the compiler substitutes the bitWidthT
type parameter and produces 32 copies of the function, which we can find in our
compiled executable with names like
github.com/Debian/dcs/internal/turbopfor/pforenc.bitpack32Unrolled[go.shape.[12]uint8]. The
shape of a generic type is based on its memory layout, so a shape for
[1]byte must be different than the shape for [2]byte.
Because the bitWidth is now known at compile time, the Go compiler can
generate close to the optimal machine code for each bit width, which we can
confirm using go tool objdump.
The code is branchless (after the one bounds check per 32 values) and aside from
the loads and stores (from/to memory) consists only of shifts and bit
operations, all with constant operands:
Now we need to actually call bitpack32 from the general bitpack function:
funcbitpack(dest[]byte,vals[]uint32,bitWidthint)[]byteifbitWidth==0returndest// no payload, sparse block with only exceptionsiflen(vals)>=32size:=4*bitWidthforlen(vals)>=32existing:=len(dest)dest=slices.Grow(dest,size)[:existing+size]bitpack32(dest[existing:]/*append*/,(*[32]uint32)(vals),bitWidth)vals=vals[32:]mask:=uint32(1<<bitWidth-1)varaccuint64varhaveintfor_,val:=rangevalsacc =uint64(val&mask)<<havehave+=bitWidthforhave>=32dest=binary.LittleEndian.AppendUint32(dest,uint32(acc))acc>>=32have-=32forhave>0dest=append(dest,byte(acc))acc>>=8have-=8returndestfuncbitpack32(dest[]byte,vals*[32]uint32,bitWidthint)switchbitWidthcase1:bitpack32Unrolled[[1]byte](dest,vals)case2:bitpack32Unrolled[[2]byte](dest,vals)case3:bitpack32Unrolled[[3]byte](dest,vals)case4:bitpack32Unrolled[[4]byte](dest,vals)case5:bitpack32Unrolled[[5]byte](dest,vals)case6:bitpack32Unrolled[[6]byte](dest,vals)case7:bitpack32Unrolled[[7]byte](dest,vals)case8:bitpack32Unrolled[[8]byte](dest,vals)case9:bitpack32Unrolled[[9]byte](dest,vals)case10:bitpack32Unrolled[[10]byte](dest,vals)case11:bitpack32Unrolled[[11]byte](dest,vals)case12:bitpack32Unrolled[[12]byte](dest,vals)case13:bitpack32Unrolled[[13]byte](dest,vals)case14:bitpack32Unrolled[[14]byte](dest,vals)case15:bitpack32Unrolled[[15]byte](dest,vals)case16:bitpack32Unrolled[[16]byte](dest,vals)case17:bitpack32Unrolled[[17]byte](dest,vals)case18:bitpack32Unrolled[[18]byte](dest,vals)case19:bitpack32Unrolled[[19]byte](dest,vals)case20:bitpack32Unrolled[[20]byte](dest,vals)case21:bitpack32Unrolled[[21]byte](dest,vals)case22:bitpack32Unrolled[[22]byte](dest,vals)case23:bitpack32Unrolled[[23]byte](dest,vals)case24:bitpack32Unrolled[[24]byte](dest,vals)case25:bitpack32Unrolled[[25]byte](dest,vals)case26:bitpack32Unrolled[[26]byte](dest,vals)case27:bitpack32Unrolled[[27]byte](dest,vals)case28:bitpack32Unrolled[[28]byte](dest,vals)case29:bitpack32Unrolled[[29]byte](dest,vals)case30:bitpack32Unrolled[[30]byte](dest,vals)case31:bitpack32Unrolled[[31]byte](dest,vals)case32:bitpack32Unrolled[[32]byte](dest,vals)
Encoding remainder blocks is quite a bit faster (full blocks use the vertical
layout anyway):
This performance win comes at the cost of binary size increase. In this case,
the .text section (executable code) grows by about 20 KB and the .gopclntab
section grows by another 26 KB. Definitely a price I am very willing to pay, but
the case might not be as clear in all circumstances.
Optimization: Bigger strides with SIMD
Even without reaching for SIMD instructions, a TurboPFor implementation can be
made faster by making it work bigger strides. Take this code from the
goturbopfor teaching decoder which counts the number of exceptions by checking
if each value s bit is set in the exception bitmap:
caseblockBitpackingExceptions:bx,input:=input[0],input[1:]n:=len(output)exmap,input:=input,input[(n+7)/8:]nex:=0// number of exceptionsfori:=rangenifexmap[i/8]&(1<<uint(i%8))!=0nex++exceptions:=d.scratch[:nex]
We can use the bits.OnesCount64
functions to count ones bits in the exception bitmap, 64 values at a time. For
remainder blocks, the rest is processed 8 values (1 byte) at a time:
i:=0for;i+8<=n/8;i+=8xm8:=binary.LittleEndian.Uint64(exmap[i:])nex+=bits.OnesCount64(xm8)for;i<(n+7)/8;i++xmb:=exmap[i]// Clear the bits which do not belong to the exception map:ifrem:=n-i*8;rem<8xmb&=1<<rem-1// Go compiles OnesCount32 into an intrinsic,// but not OnesCount8, so we convert to uint32:nex+=bits.OnesCount32(uint32(xmb))
OnesCount64 uses a 64-bit register. For comparison, AVX2 SIMD instructions use
256-bit registers (= 8 uint32) and AVX512 SIMD instructions use 512-bit registers.
In the following sections, we will first set up our build tags for conditional
compilation to use a trivial SIMD instruction, then walk through an AVX2 and
AVX512 SIMD kernel.
SIMD build tags
Let s assume we have the following scalar code:
constant.go:
To increase throughput, we can use AVX2 instructions if they are available on the CPU on which the program runs, i.e. using runtime dispatch. We ll first rename fillConstant to fillConstantScalar (it s now the fallback path):
constant.go:
Next, we ll supply two different implementations (constant_nosimd.go and constant_amd64.go), the latter of which is selected when compiling for GOARCH=amd64 with GOEXPERIMENT=simd (the latter will hopefully be dropped in a later version of Go). The nosimd variant just dispatches to the fillConstantScalar, which will likely be inlined:
The constant_amd64.go variant assigns the hasAVX2 global variable by doing a CPUID check and then jumps to the scalar fallback if !hasAVX2, i.e. the CPU is too old:
//go:build goexperiment.simd && amd64packagepfordecimport"simd/archsimd"varhasAVX2=archsimd.X86.AVX2()funcfillConstant(output[]uint32,valuint32)if!hasAVX2fillConstantScalar(output,val)returnval8:=archsimd.BroadcastUint32x8(val)i:=0for;i+8<=len(output);i+=8val8.StoreArray((*[8]uint32)(output[i:i+8]))// use the scalar implementation for the last <= 7 elementsfillConstantScalar(output[i:],val)
We can go one step further by conditionally compiling const hasAVX2 = true
when GOAMD64 is set to v3 or higher (i.e. the amd64.v3 build tag is
set). As a practical example from Debian Code Search, we currently need the
following checks / dispatches:
In regular (non-SIMD) bitpacking, integers are stored on disk one after
the other, padded to a full byte, as a byte is the smallest addressable unit
when reading data from disk. For example, if you bitpack only one 3 bit int,
you will end up with 5 bits of padding.
SIMD bitpacking works like regular bitpacking, but processes 8 uint32
little-endian values at the same time, leveraging the AVX instruction
set. The following
illustration shows the order in which 3-bit integers are decoded from disk:
The scalar implementation uses an array of 8 uint64 to process 8 values at a
time:
funcbitunpack256v32(input[]byte,dest[]uint32,bitWidthint)(readint)mask:=uint64(1)<<bitWidth-1orig:=len(input)varbitsuintvaracc[8]uint64// accumulator: current+next bitsforop:=0;op<len(dest);ifbits<uint(bitWidth)// read 8 more uint32sfori:=range8acc[i] =uint64(binary.LittleEndian.Uint32(input))<<bitsinput=input[4:]bits+=32fori:=range8dest[op]=uint32(acc[i]&mask)op++acc[i]>>=bitWidthbits-=uint(bitWidth)returnorig-len(input)
The SIMD version also processes 8 values, but without a for i := range 8 loop!
One difference is that we no longer have the luxury of using uint64 for acc
(holding rest and current bits); because AVX2 registers only fit 8 uint32 (not
8 uint64). Instead, we split acc into rest8 and cur8.
funcbitunpack256v32(fullinput[]byte,fulldest[]uint32,bitWidthint)(readint)dest:=fulldest[:256]ifbitWidth==0clear(dest)return0n:=32*int(bitWidth)input:=fullinput[:n]// tell the Go compiler how long the input ismask8:=archsimd.BroadcastUint32x8(uint32(1)<<bitWidth-1)bitWidth8:=archsimd.BroadcastUint32x8(uint32(bitWidth))varbitsuintpos:=0// var acc [8]uint64varrest8archsimd.Uint32x8varcur8archsimd.Uint32x8forop:=0;op<256;op+=8ifbits<uint(bitWidth)// read 8 more uint32s// acc[i] = uint64(binary.LittleEndian.Uint32(input)) << bitsnext:=archsimd.LoadUint8x32(input[pos:pos+32]).ReshapeToUint32s()pos+=32// input = input[4:]cur8=rest8.Or(next.ShiftAllLeft(uint64(bits)))// acc[i] >>= bitWidthrest8=next.ShiftAllRight(uint64(uint(bitWidth)-bits))bits+=32elsecur8=rest8// acc[i] >>= bitWidthrest8=rest8.ShiftRight(bitWidth8)// dest[op] = uint32(acc[i] & mask)cur8.And(mask8).Store(dest[op:op+8])bits-=uint(bitWidth)returnn
The SIMD version benchmarks about 3x as fast as the scalar version.
Another significant speedup is to use generics for bit width
specialization for this SIMD kernel so that
bitWidth becomes a compile-time constant and the compiler can generate better
code.
Positional Popcount
For my TurboPFor encoder, I implemented the same techniques as described above:
These changes are sufficient to roughly match the cgo performance, but then
Claude Fable 5 found another 2x speed-up on top of that!
The key observation is that once encoding blocks is fast, the preceding step of
scanning the input values to decide which block type to use becomes the
bottleneck. Here is the encoder s main encode function, which first does one
pass over the input values (scan) and then prices all different block types at
all relevant bit widths (requires fast access to the scan histogram):
func(be*BlockEncoder)encode(dest[]byte,vals[]uint32,layoutblockLayout)[]bytevarstatsstatsscan(&stats,vals)// gathers statistics from every value in valsbitWidth:=bits.Len32(stats.or)ifstats.or==stats.andreturnbe.encodeConstant(dest,vals,bitWidth)n:=len(vals)// bitpacking is the default, unless we find a more efficient block type.bestType:=blockBitpackingbestB:=bitWidthbest:=priceBitpack(n,bitWidth,layout)// Walk from high bitWidths to low: to break ties, we prefer// the encoding with fewer exceptions (for faster decoding).forb:=bitWidth-1;b>=0;b--// up to 32 iterationsnex:=int(stats.cnt[b])size:=priceBitpackExceptions(n,b,bitWidth,nex,layout)ifsize<bestbestType=blockBitpackingExceptionsbestB=bbest=size// Over-approximate the number of VB bytes.vb:=nex+// exceptions using 1, 2, 3, 4, or 5 VB bytesint(stats.cnt[b+7]+// exceptions using 2, 3, 4, or 5 VB bytesstats.cnt[b+14]+// exceptions using 3, 4, or 5 VB bytesstats.cnt[b+19]+// exceptions using 4 or 5 VB bytesstats.cnt[b+24])// exceptions using 5 VB bytessize=headerBytes+headerExBytes+payloadBytes(n,b,layout)+vb+nexifsize<bestbestType=blockBitpackingVBExceptionsbestB=bbest=sizeswitchbestTypecaseblockBitpacking:returnbe.encodeBitpack(dest,vals,layout,bitWidth)caseblockBitpackingExceptions:returnbe.encodeBitpackExc(dest,vals,layout,bestB,bitWidth-bestB)caseblockBitpackingVBExceptions:returnbe.encodeBitpackVBExc(dest,vals,layout,bestB,int(stats.cnt[bestB]))default:panic("BUG: bestType not implemented")
I ll show you a slightly shortened version of scan, the function which is the bottleneck:
typestatsstruct// cnt[n] = how many values where bits.Len32(val)>n,// i.e. how many exceptions are required for bitWidth=n.// Padded so that cnt[b+24] is always in bounds.cnt[32+24]uint32funcscan(output*stats,vals[]uint32)for_,val:=rangevalsforb:=rangebits.Len32(val)output.cnt[b]++// b bits are not enough to store val
Let s consider the following 3 example values to understand the resulting cnt:
input
input (bin)
bits.Len32
23
0b0000010111
5
5
0b0000000101
3
666
0b1010011010
10
The resulting cnt exception count histogram would contain (cnt shortened to c):
c[0]
c[1]
c[2]
c[3]
c[4]
c[5]
c[6]
c[7]
c[8]
c[9]
c[10]
3
3
3
2
2
1
1
1
1
1
0
In words, this means that at bit width 10, we could encode all the values
without any exceptions.
But most values do not need 10 bits, so a bit width of 5 would be more
efficient, but requires storing one exception. Encoding at bit width 4 requires
2 exceptions, and so on.
The scan function above is intentionally kept simple for illustration. We can
make it faster by moving the per-bit-width loop outside the per-element
loop.
The fast version still needs about 12 instructions per value. With SIMD, we can
reduce this to by 8x to only 1.5 instructions per value!
The trick: smear masks enable positional popcount
The trick is to turn each input value into its smear mask (imagine taking the
first 1 bit and smearing it across the remaining positions). Here are the smear
masks for our example:
input
input (bin)
bits.Len32
smear mask
23
0b0000010111
5
0b0000011111
5
0b0000000101
3
0b0000000111
666
0b1010011010
10
0b1111111111
Turning a value into its smear mask is computationally cheap:
Go implements BitLen(x) (functions like bits.Len32) by calculating 32 - LZCNT(x). We can calculate the smear mask of a value with ^uint32(0) >> LZCNT(x), i.e. starting with a 32-one-bits mask and shifting it by the number
of leading zeros.
Now, to obtain e.g. cnt[4], we can count the 1 bits at bit position 4 of all
input values.
The POPCNT instruction counts bits very efficiently, but it counts one bits
within a register, so it counts rows, not columns. Counting columns is called
Positional Population Count.
I found the following papers that describe positional popcount with SIMD:
Positional Popcount: a visual explanation
To understand the AVX512 implementation of positional popcount, I found it most
helpful to visualize an AVX512 register (512 bits, i.e. 64 bytes). The graphic
below uses the Uint64x8 layout, meaning it divides the register into 8 lanes
of 64 bits (= 8 bytes) each.
This illustration shows the whole process: how uint32s are loaded into an
AVX512 register (all 4 of its bytes, in sequence) and where we end up, i.e. the
32 positional popcounts:
Let s break down this process into its individual steps.
First, we turn each loaded value into its smear mask as explained above.
The VPOPCNTB vector instruction calculates POPCNT (1 byte) of 64 bytes at
once, but first we need to shuffle the bytes inside the register: in load
order, we have a full uint32 (4 bytes), followed by another uint32, per
lane. First, we permute the bytes (VPERMB) such that all the first bytes of
each value end up in one lane ( transpose the bytes ):
Next, we transpose the bits using the GF2P8AFFINEQB instruction, which
sounds scary but turns out to be quite flexible for bit manipulation of all
kinds. The GF2P8AFFINEQB instruction is also the star of the show in Go s
Green Tea Garbage Collector (2025). Here is the
bit transpose, shown in the AVX512 register layout (see below for a different
layout):
I found it easier to understand the transpose step when arranging the 8 bytes of
lane 0 from top-to-bottom (instead of left-to-right), because then it looks like
a 90 degree clockwise rotation:
Now we can use VPOPCNTB to count the bits in all 64 bytes at once:
After all loop iterations (processing 16 values each) are done, we add the two
groups (first 8 values, second 8 values) to obtain the 32 exception counts:
Positional Popcount: Go SIMD
Here is the Go code that implements what I described visually above:
funcscanSIMD(output*stats,vals[]uint32)ones16:=archsimd.BroadcastUint32x16(^uint32(0))// 16 32-one-bits masksshuffle:=archsimd.LoadUint8x64Array(&scanShuffle)units:=archsimd.LoadUint8x64Array(&scanUnits)varaccarchsimd.Uint8x64idx:=0for;idx+16<=len(vals);idx+=16v:=archsimd.LoadUint32x16(vals[idx:idx+16])// Replace all values with their smear masks.smear:=ones16.ShiftRight(v.LeadingZeros()).ReshapeToUint8s()// Transpose: shuffle the bytes, then transpose the bits.matrices:=smear.Permute(shuffle).ReshapeToUint64s()transposed:=units.GaloisFieldAffineTransform(matrices,0)// Popcount 64 bytes at once into the accumulator.acc=acc.Add(transposed.OnesCount())// Store the accumulator into output.cnt:// Widen the two groups of byte counts to uint16 lanes (so that// 128+128 = 256 fits), fold them into cnt[b] for b=0..31,// then widen again to the uint32 lanes of output.cnt.sum:=acc.GetLo().ExtendToUint16().Add(acc.GetHi().ExtendToUint16())sum.GetLo().ExtendToUint32().Store(output.cnt[0:16])sum.GetHi().ExtendToUint32().Store(output.cnt[16:32])// scalar tail for the 0..15 remaining valuesfor_,val:=rangevals[idx:]forb:=rangebits.Len32(val)output.cnt[b]++
Go even faster?
The SIMD optimizations I showed above beat the cgo TurboPFor library that Debian
Code Search used before. When comparing apples to apples, i.e. backporting the
AVX512 kernels and positional popcount technique to C TurboPFor, Go benchmarks a
little slower at 1.4x C.
Could we make my Go TurboPFor implementation even faster, to truly match the C
speed?
Yes! But also no. Let me explain:
We could use more SIMD instructions to remove all code that still processes
one value at a time. For example, in my encoder s encodeBitpackVBExc
function. Or we could price all bit widths concurrently in encode. Or in
the decoder s exception apply code path.
But all of these SIMD instructions
make understanding (and changing) the code harder, so I am cautious regarding
which ones I introduce.
A big part of the performance gap is due to Go s bounds
checks. While it costs
performance, bounds checking is great for safety, so I will not turn off
bounds checking. The Go compiler eliminates a number of bounds checks when it
understands it s safe to do so. One optimization avenue could be to make the
prove pass in the Go compiler smarter to eliminate more bounds checks.
When doing mid-stack inlining (proposal
#19348)
(2017), Go sometimes needs to put NOP instructions into the binary so that
it can attach inlining markers. For dispatch-bound functions, these extra
NOPs can measurable slow down execution.
The Go compiler currently allows specifying the architecture (GOARCH=amd64)
and microarchitecture (GOAMD64=v3), but not a specific CPU architecture
(like AMD Zen 4). Therefore, CPU-specific workarounds for one vendor affect
all the generated code. The specific one I encountered in my code is that the
Go compiler emits XORL CX,CX before every POPCNT to break a
false-output-dependency from the Intel Sandy Bridge Skylake era, which is
unnecessary on AMD Zen CPUs.
I suspect that Go intentionally does not offer this level of customizability.
After all of the above points are addressed, what remains is better code
generation in specific cases. To illustrate what I mean, consider the example
of incrementing a loop variable, where Go re-derives an index every time:
Go: POPCNTL; ADDQ DI,CX; LEAQ (base)(CX*4) (3 instructions)
clang: popcnt; lea rax,[rax+4*rdi] (2 instructions)
Depending on the specific case, improving the compiler might be easy or
prohibitively complex. Often, such improvements are hard to measure conclusively.
Conclusion
Go s SIMD support makes available in Go code without having to resort to cgo
or assembly a powerful part of modern CPUs which allows speeding up the kind
of computation that TurboPFor needs by an order of magnitude!
I found it very valuable to use a coding agent (Claude Code, with Opus 5 and
Fable 5 in this case) to help with the many tedious parts of such performance
work (and still it took me weeks!). The LLM can read objdump output much faster
than I can, can see patterns and correlations I might never identify, never
becomes frustrated after a compiler error or runtime panic, and never runs out
of patience to run one more experiment, as long as I give it measurable and
reachable goals.
The performance of the SIMD code which one can get from the Go compiler is
pretty close to what a good C compiler like clang provides. The CPU performance
counters show value decoding speeds of 7 instructions/cycle (IPC) on a machine
where the maximum is 8 IPC.
To me, SIMD support is a very welcome addition to Go.
I just released a new version of PyKCS11, a Python wrapper above
the PKCS#11 API.
See PyKCS11 introduction or PyKCS11 s documentation.
The project is registered at Pypi: https://pypi.org/project/PyKCS11/
Explanation
This version only fixes a problem on Windows.
In version 1.5.19, I upgraded
the PKCS#11 header file pkcs11.h to version PKCS#11 3.2.
Execution of automatic tests failed on Windows. I then disabled
failed test. But I, in fact, disabled all the tests on
Windows. And the problem went unnoticed.
Version 1.5.19 did not contain the code required
to pack the structures on Windows. So the PyKCS11 wrapper and the
PKCS#11 library were not alligned on the data format. And crash...
Changes:
1.5.20 - September 2026, Ludovic Rousseau
The MX record and some TXT records configured for 
The Poppler transition tracker identifies the old and new runtime library package names.
I added 
A Poppler test showing the selected rebuild jobs. Three jobs reached the CI timeout, they were not confirmed package regressions.
I also changed 
This is a new series
I ve long been interested in hardware key material storage devices. I ve been
a fan of 
The Reproducible Builds project 
I m looking at something entirely unrelated, but tripped over some search results that made me realise that a lot of people still think getting errors like 
However, when playing it, it becomes very obvious (as you can likely see) that
there s a fair amount of packet loss (understandable) and probably some packet
collisions taking place.
After tweaking the local routing tables (and restarting 
Yes! I forgot to make this one a video, so no gif. I did wind up having a bit
if trouble with a few gopher clients and IPv6 support I may send some
patches if I can find the time.
Given i m going to stub most of that out, let s take a look at what some
similar Layer 2 protocols use things like Ethernet or WiFi frames. Both
contain structured information regarding the transmitter, desired recipient,
type of data, and the higher-level data itself (such as IP packets). As a
result of attempting to learn from others, the Pigeon Layer 2 (called, simply,
My Debian contributions this month were all 
The 
SIMD bitpacking works like regular bitpacking, but processes 8 
I just released a new version of