2023-05-28 – Where does "where does my computer get the time from?" come from?

I am pleased that so many people enjoyed my talk about time at RIPE86. I thought I would write a few notes on some of the things I left out.

read more ...


2023-05-26 – Where does my computer get the time from?

This week I was in Rotterdam for a RIPE meeting. On Friday morning I gave a lightning talk called where does my computer get the time from? The RIPE meeting website has a copy of my slides and a video of the talk; this is a blogified version, not an exact transcript.

read more ...


2023-05-22 – RIPE DNS Hackathon

This weekend I was in Rotterdam for the RIPE DNS Hackathon.

About 50 people gathered with several ideas for potential projects: things like easier DNSSEC provisioning, monitoring DNS activity in the network, what is the environmental cost of the DNS, …

At the start of the weekend we were asked to introduce ourselves and say what our goals were. My goal was to do something different from my day job working on BIND. I was successful, tho I did help some others out with advice on a few of BIND’s obscurities.

The team I joined was very successful at producing a working prototype and a cool demo.

read more ...


2023-02-28 – A qp-trie for BIND

In 2021, I came up with a design for a new memory layout for a qp-trie, and I implemented a prototype of the design in NLnet Labs NSD (see my git repo or github).

Since I started work at ISC my main project has been to adapt the NSD prototype into a qp-trie for use in BIND. The ultimate aim is to replace BIND’s red-black tree database, its in-memory store of DNS records.

Yesterday I merged the core qp-trie implementation into BIND so it’s a good time to write some blog notes about it.

The core of the design is still close to what I sketched in 2021 and implemented in NSD, so these notes are mostly about what’s different, and the mistakes I made along the way…

read more ...


2023-02-12 – libc delenda est

Chris Wellons posted a good review of why large chunks of the C library are terrible, especially if you are coding on Windows - good fun if you like staring into the abyss. He followed up with let’s write a setjmp which is fun in a more positive way. I was also pleased to learn about __builtin_longjmp! There’s a small aside in this article about the signal mask, which skates past another horrible abyss - which might even make it sensible to DIY longjmp.

Some of the nastiness can be seen in the POSIX rationale for sigsetjmp which says that on BSD-like systems, setjmp and _setjmp correspond to sigsetjmp and setjmp on System V Unixes. The effect is that setjmp might or might not involve a system call to adjust the signal mask. The syscall overhead might be OK for exceptional error recovery, such as Chris’s arena out of memory example, but it’s likely to be more troublesome if you are implementing coroutines.

But why would they need to mess with the signal mask? Well, if you are using BSD-style signals or you are using sigaction correctly, a signal handler will run with its signal masked. If you decide to longjmp out of the handler, you also need to take care to unmask the signal. On BSD-like systems, longjmp does that for you.

The problem is that longjmp out of a signal handler is basically impossible to do correctly. (There’s a whole flamewar in the wg14 committee documents on this subject.) So this is another example of libc being optimized for the unusual, broken case at the cost of the typical case.


2023-01-27 – What does it mean to be an RCU implementation?

The other day, Paul McKenney posted an article on LiveJournal about different flavours of RCU, prompted by a question about couple of Rust RCU crates. (There are a few comments about it on LWN.)

McKenney goes on to propose an RCU classification system based on the API an implementation provides to its users. (I am curious that the criteria do not involve how RCU works.)

Here’s how I would answer the questions for QSBR in BIND:


2023-01-24 – Concurrent qp-trie performance numbers

Previously, I wrote about implementing safe memory reclamation for my qp-trie code in BIND. I have now got it working with a refactored qp-trie that has been changed to support asynchronous memory reclamation - working to the point where I can run some benchmarks to compare the performance of the old and new versions.

read more ...


2023-01-14 – Cataract surgery

Previously, I wrote about my cataract and its assessment at Addenbrooke’s cataract clinic.

I had my cataract removed a couple of weeks ago, and so far things are going well, though there is still some follow-up work needed.

read more ...


2023-01-10 – Safe memory reclamation for BIND

At the end of October, I finally got my multithreaded qp-trie working! It could be built with two different concurrency control mechanisms:

OK, but I want the best of both worlds! To fix it, I needed to change the qp-trie code to use safe memory reclamation more effectively: instead of blocking inside synchronize_rcu() before cleaning up, use call_rcu() to clean up asynchronously. I expect I’ll write about the qp-trie changes another time.

Another issue is that I want the best of both worlds by default, but liburcu is LGPL and we don’t want BIND to depend on code whose licence demands more from our users than the MPL.

So I set out to write my own safe memory reclamation support code.

read more ...


2022-12-12 – Slower DNS name decompression

In a previous entry, I wrote about making DNS name decompression faster by moving work left on this diagram so that we do less of it:

    names < pointers < labels < bytes

Last week I had a bright idea about that leftmost step, moving per-pointer work to per-name, using some dirty tricks. Sadly the experiment was not successful, because it also increased the per-label work. Nevertheless I think it’s interesting enough to be worth writing about.

read more ...


2022-12-05 – BIND zone transfer performance

This year I have rewritten BIND’s DNS name compression and decompression code. I didn’t plan to, it just sort of happened! Anyway, last week my colleague Petr was doing some benchmarking, and he produced some numbers that seemed too good to be true, so I have re-done the measurement myself, and wow.

read more ...


2022-12-04 – An update on leap seconds

It has been a couple of years since my previous blog post about leap seconds, though I have been tweeting on the topic fairly frequently: see my page on date, time, and leap seconds for an index of threads. But Twitter now seems a lot less likely to stick around, so I’ll aim to collect more of my thinking-out-loud here on my blog.

read more ...


2022-11-17 – Faster DNS name decompression

Earlier this year, I rewrote BIND’s DNS name compression algorithm. That work is in the November release, BIND 9.19.7.

Last week I rewrote the reverse algorithm, DNS name decompression, and made it about 2x faster. I enjoyed deleting this comment that dates back to January 1999:

/*
 * Note:  The following code is not optimized for speed, but
 * rather for correctness.  Speed will be addressed in the future.
 */

So here is a collection of folklore and tricks related to DNS name decompression.

read more ...


2022-10-12 – hg64 multithreaded histograms

Since my blog post about hg64 histograms in July I have continued occasional hacking on the code, so it’s time to post an update.

As before, my proof-of-concept histogram data structure hg64 is available from:

read more ...


2022-09-23 – How big is this integer type?

This week I am on “escalation engineer” duty, which means triaging new bug reports. One of them was found by ubsan (-fsanitize=undefined) reporting an overflow in a signed integer shift. This was fun to fix because it needed a bit of lateral thinking.

read more ...


2022-07-15 – hg64: a 64-bit histogram data structure

See 2022-10-12 for an update

I have reached the point in my main project (qp-trie for BIND) where I want to collect performance statistics. Things like:

In a wider context, those using BIND for large authoritative server systems would like better statistics on things like:

For my own purposes, I’m no longer satisfied with summarizing performance with just the mean and standard deviation; and in an operational context, it’s useful to know about the existence of outliers (rare outliers can be hidden by simple summary statistics) and the size of an outlier can be a useful clue.

So, we need histograms!

hg64

I have written a proof-of-concept histogram data structure called hg64, which you can get from:

It can load 1 million data items in about 5ms (5ns per item), and uses a few KiB of memory.

Here I will write about how hg64 came to be.

read more ...


2022-07-01 – A DNS name compression algorithm

In our previous episode, I optimized tolower() using SWAR tricks. That was in fact a side-quest to a side-quest to a side-quest. The first side-quest was trying out a new DNS name compression algorithm; in BIND, compression is performance-critical and a heavy user of tolower(), which is what set me off on the second and third side-quests.

Now let’s pop the stack, and talk about DNS names.

read more ...


2022-06-27 – tolower() in bulk at speed

Here’s a fun bit of Monday optimization.

DNS servers often have to convert DNS names to their canonical lower case form. BIND has to do so a bit more than most because it tries to preserve the case of DNS names rather than canonicalizing them.

I was recently distracted by a cleanup oportunity: there were multiple maptolower lookup tables in BIND, so I decided to make a home for them so that we would only need one copy. Then I thought, surely there are faster ways to implement tolower() than a lookup table.

read more ...


2022-06-22 – Compacting a qp-trie

My new job is working on BIND for ISC, and my main project is to replace BIND’s core red-black tree data structure with my qp-trie.

previously

In the summer of 2021 I wrote some notes on page-based GC for qp-trie RCU which I then went on to implement in my fork of NSD.

Since the start of May 2022 I have ported the NSD version of my qp-trie to BIND, with several improvements:

The notes I wrote last summer turned into code very nicely: NSD proved to be a good place to try out the ideas. And more recently, I am pleased with how the code adapted to the more complicated demands of BIND.

But there’s one area that has been problematic: compaction.

read more ...


2022-06-04 – Choice on Units of Measurement: Markings and Sales

My response to the UK government consultation on using imperial units of measure for retail.

Regarding the foreword to the consultation description, my children were weighed in kilos at birth, so whoever wrote the foreword must be wery old, and talking about babies who are now grown adults.

And for metrological purposes, British weights and measures have been derived from the metric system since the international convention on the metre in 1875 and the production of the new metric prototypes in London in 1898, because the metric standards were made to a higher quality with greater reliability than the old imperial standards. So it’s incorrect to say that we started adopting the metric system in 1995; that was actually when we started abolishing imperial (and that was at the initiative of the UK government, not the EU).

oops, I should have mentioned that the tories were in power in 1995

Q. 1 for all,

1 a) Are there any specific areas of consumer transactions that should be a priority for allowing a choice in units of measurement, and why?

None, because there is no need to make it more confusing to compare sizes and prices.

1 b) Are there any specific areas that you think should be excluded from a choice in units of measurement, and why?

There should be a single set of standard units of measure so that it is as easy as possible to compare the sizes and prices of goods, especially (e.g.) price per kilo or price per litre.

1 c) If an item is sold in imperial measures, should there be a requirement for a metric equivalent alongside it?

Metric measures should always be required, and there should always be clear labelling showing the price per some power of 10 (e.g. 100g or 1kg)

Q. 2 for businesses,

n/a (I am replying as an individual)

Q. 3 for consumers,

3 a) If you had a choice, would you want to purchase items:

I always want to purchase items in metric (preferably a round number when measured in metric units), and I want it to be easy to find the quantity labelled in metric.

3 b) Are you more likely to shop from businesses that sell in imperial units?

I am likely to avoid shops that use imperial units, because the measurements will be confusing and unfamiliar.

3 c) Do you foresee any costs or benefits to you from businesses being permitted to sell:

I expect it will be detrimental to allow businesses to sell in imperial units only, because it will make it easier for them to confuse customers, misprice goods, and hide their malpractice.

3 d) Do you have experience of buying solely in imperial units?

I am 47 years old and I cannot remember when imperial measures were in wide use for anything except milk and beer.

Milk, for example, is often confusing when 2 litre bottles are sold alongside 4 pint bottles, and I have to carefully examine the labels to find out which is the larger volume and what is the price per litre of the 4 pint bottle.

For beer, how can I compare a pint bottle and a 33cl bottle? It’s relatively easy for 50cl vs 33cl because the ratio is 3/2. In practice I think of a pint as about half a litre, so I can compare in metric. And, when I am served beer in a pub in a pint-to-brim glass, what I usually get is closer to half a litre than a pint.

Q. 4 for trading standards,

n/a (I am replying as an individual)