Tony Finch's blog

I recently saw FixedFixer on Hacker News. This is a bookmarklet which turns off CSS position:fixed, which makes a lot of websites less annoying. Particular offenders include Wired, Huffington Post, Medium, et cetera ad nauseam. A lot of them are unreadable on my old small phone because of all the crap they clutter up the screen with, but even on my new bigger phone the clutter is annoying. Medium's bottom bar is particularly vexing because it looks just like mobile Safari's bottom bar. Bah, thrice bah, and humbug! But, just run FixedFixer and the crap usually disappears.

The code I am using is very slightly adapted from the HN post. In readable form:

  (function(elements, elem, style, i) {
    elements = document.getElementsByTagName('*');
    for (i = 0; elem = elements[i]; i++) {
      style = getComputedStyle(elem);
      if (style && style.position == 'fixed')
        elem.style.position = 'static';
    }
  })();

Or in bookmarklet style:
javascript:(function(ee,e,s,i){ee=document.getElementsByTagName('*');for(i=0;e=ee[i];i++){s=getComputedStyle(e);if(s&&s.position=='fixed')e.style.position='static';}})();

Adding bookmarklets in iOS is a bit annoying because you can't edit the URL when adding a bookmark. You have to add a rubbish bookmark then as a separate step, edit it to replace the URL with the bookmarklet. Sigh.

I have since added a second bookmarklet, because when I was trying to read about AWS a large part of the text was off the right edge of the screen and they had disabled scrolling and zooming so it could not be read. How on earth can they publish a responsive website which does not actually work on a large number of phones?!

Anyway, OverflowFixer is the same as FixedFixer, but instead of changing position='fixed' to position='static', it changes overflow='hidden' to overflow='visible'.

When I mentioned these on Twitter, Tom said "Please share!" so this is a slightly belated reply. Do you have any bookmarklets that you particularly like? Write a comment!

A lot of my day has been spent on the POODLE vulnerability. For details see the original paper, commentary by Daniel Franke, Adam Langley, Robert Graham, and the POODLE.io web page of stats and recommendations.

One thing I have been investigating is to what extent mail software uses SSLv3. The best stats we have come from our message submission server, smtp.hermes, which logs TLS versions and cipher suites and (when possible) User-Agent and X-Mailer headers. (The logging from our POP and IMAP servers is not so good, partly because we don't request or log user agent declarations, and even if we did most clients wouldn't provide them.)

Nearly 100 of our users are using SSLv3, which is about 0.5% of them. The main culprits seem to be Airmail, Evolution, and most of all Android. Airmail is a modern Mac MUA, so in that case I guess it is a bug or misuse of the TLS API. For Evolution my guess is that it has a terrible setup user interface (all MUAs have terrible setup user interfaces) and users are choosing "SSL 3.0" rather than "TLS 1.0" because the number is bigger. In the case of Android I don't have details of version numbers because Android mail software doesn't include user-agent headers (unlike practically everything else), but I suspect old unsupported smart-ish phones running bad Java are to blame.

I haven't decided exactly what we will do to these users yet. However we have the advantage that POODLE seems to be a lot less bad for non-web TLS clients.

The POODLE padding oracle attack requires a certain amount of control over the plaintext which the attacker is trying to decrypt. Specifically:

1. The plaintext plus MAC has to be an exact multiple of the cipher block size;
2. It must be possible to move the secret (cookie or password) embedded in the plaintext by a byte at a time to scan it past a block boundary.

In the web situation, the attacker can use JavaScript served from anywhere to make repeated POST requests to an arbitrary target host. The JS can manipulate the body of the POST to control the overall length of the request, and can manipulate the request path to control the position of the cookie in the headers.

In the mail situation (POP, IMAP, SMTP), the attacker can make the client retry requests repeatedly by breaking the connection, but they cannot control the size or framing of the client's authentication command.

So I think we have the option of not worrying too much if forced upgrades turn out to be too painful, though I would prefer not to go that route - it makes me feel uncomfortably complacent.

One of the great promises of DNSSEC is to provide a new public key infrastructure for authenticating Internet services. If you are a relatively technical person you can try out this brave new future now with ssh.

There are a couple of advantages of getting SSHFP host authentication to work. Firstly you get easier-to-use security, since you longer need to rely on manual host authentication, or better security for the brave or foolhardy who trust leap-of-faith authentication. Secondly, it becomes feasible to do host key rollovers, since you only need to update the DNS - the host's key is no longer wired into thousands of known_hosts files. (You can probably also get the latter benefit using ssh certificate authentication, but why set up another PKI if you already have one?)

In principle it should be easy to get this working but there are a surprising number of traps and pitfalls. So in this article I am going to try to explain all the whys and wherefores, which unfortunately means it is going to be long, but I will try to make it easy to navigate. In the initial version of this article I am just going to describe what the software does by default, but I am happy to add specific details and changes made by particular operating systems.

The outline of what you need to do on the server is:

• Sign your DNS zone. I will not cover that in this article.
• Publish SSHFP records in the DNS

The client side is more involved. There are two versions, depending on whether ssh has been compiled to use ldns or not. Run ldd $(which ssh) to see if it is linked with libldns.

• Without ldns:
  • Install a validating resolver (BIND or Unbound)
  • Configure the stub resolver /etc/resolv.conf
  • Configure ssh
• With ldns:
  • Install unbound-anchor
  • Configure the stub resolver /etc/resolv.conf
  • Configure ssh

Publish SSHFP records in the DNS

Generating SSHFP records is quite straightforward:

    demo:~# cd /etc/ssh
    demo:/etc/ssh# ssh-keygen -r $(hostname)
    demo IN SSHFP 1 1 21da0404294d07b940a1df0e2d7c07116f1494f9
    demo IN SSHFP 1 2 3293d4c839bfbea1f2d79ab1b22f0c9e0adbdaeec80fa1c0879dcf084b72e206
    demo IN SSHFP 2 1 af673b7beddd724d68ce6b2bb8be733a4d073cc0
    demo IN SSHFP 2 2 953f24d775f64ff21f52f9cbcbad9e981303c7987a1474df59cbbc4a9af83f6b
    demo IN SSHFP 3 1 f8539cfa09247eb6821c645970b2aee2c5506a61
    demo IN SSHFP 3 2 9cf9ace240c8f8052f0a6a5df1dea4ed003c0f5ecb441fa2c863034fddd37dc9

Put these records in your zone file, or you can convert them into an nsupdate script with a bit of seddery:

    ssh-keygen -r $(hostname -f) |
        sed 's/^/update add /;s/ IN / 3600 IN /;/ SSHFP . 1 /d;'

The output of ssh-keygen -r includes hashes in both SHA1 and SHA256 format (the shorter and longer hashes). You can discard the SHA1 hashes.

It includes hashes for the different host key authentication algorithms:

• 1: ssh-rsa
• 2: ssh-dss
• 3: ecdsa

I believe ecdsa covers all three key sizes which OpenSSH gives separate algorithm names: ecdsa-sha2-nistp256, ecdsa-sha2-nistp384, ecdsa-sha2-nistp521

OpenSSH supports other host key authentication algorithms, but unfortunately they cannot be authenticated using SSHFP records because they do not have algorithm numbers allocated.

The problem is actually worse than that, because most of the extra algorithms are the same as the three listed above, but with added support for certificate authentication. The ssh client is able to convert certificate to plain key authentication, but a bug in this fallback logic breaks SSHFP authentication.

So I recommend that if you want to use SSHFP authentication your server should only have host keys of the three basic algorithms listed above.

NOTE (added 26-Nov-2014): if you are running OpenSSH-5, it does not support ECDSA SSHFP records. So if your servers need to support older clients, you might want to stick to just RSA and DSA host keys.

You are likely to have an SSHFP algorithm compatibility problem if you get the message: "Error calculating host key fingerprint."

NOTE (added 12-Mar-2015): if you are running OpenSSH-6.7 or later, it has support for Ed25519 SSHFP records which use algorithm number 4.

Install a validating resolver

To be safe against active network interception attacks you need to do DNSSEC validation on the same machine as your ssh client. If you don't do this, you can still use SSHFP records to provide a marginal safety improvement for leap-of-faith users. In this case I recommend using VerifyHostKeyDNS=ask to reinforce to the user that they ought to be doing proper manual host authentication.

If ssh is not compiled to use ldns then you need to run a local validating resolver, either BIND or unbound.

If ssh is compiled to use ldns, it can do its own validation, and you do not need to install BIND or Unbound.

Run ldd $(which ssh) to see if it is linked with libldns.

Install a validating resolver - BIND

The following configuration will make named run as a local validating recursive server. It just takes the defaults for everything, apart from turning on validation. It automatically uses BIND's built-in copy of the root trust anchor.

/etc/named/named.conf

    options {
        dnssec-validation auto;
        dnssec-lookaside auto;
    };

Install a validating resolver - Unbound

Unbound comes with a utility unbound-anchor which sets up the root trust anchor for use by the unbound daemon. You can then configure unbound as follows, which takes the defaults for everything apart from turning on validation using the trust anchor managed by unbound-anchor.

/etc/unbound/unbound.conf

    server:
        auto-trust-anchor-file: "/var/lib/unbound/root.key"

Install a validating resolver - dnssec-trigger

If your machine moves around a lot to dodgy WiFi hot spots and hotel Internet connections, you may find that the nasty middleboxes break your ability to validate DNSSEC. In that case you can use dnssec-trigger, which is a wrapper around Unbound which knows how to update its configuration when you connect to different networks, and which can work around braindamaged DNS proxies.

Configure the stub resolver - without ldns

If ssh is compiled without ldns, you need to add the following line to /etc/resolv.conf; beware your system's automatic resolver configuration software, which might be difficult to persuade to leave resolv.conf alone.

    options edns0

For testing purposes you can add RES_OPTIONS=edns0 to ssh's environment.

On some systems (including Debian and Ubuntu), ssh is patched to force EDNS0 on, so that you do not need to set this option. See the section on RRSET_FORCE_EDNS0 below for further discussion.

Configure the stub resolver - with ldns

If ssh is compiled with ldns, you need to run unbound-anchor to maintain a root trust anchor, and add something like the following line to /etc/resolv.conf

    anchor /var/lib/unbound/root.key

Run ldd $(which ssh) to see if it is linked with libldns.

Configure ssh

After you have done all of the above, you can add the following to your ssh configuration, either /etc/ssh/ssh_config or ~/.ssh/config

    VerifyHostKeyDNS yes

Then when you connect to a host for the first time, it should go straight to the Password: prompt, without asking for manual host authtentication.

If you are not using certificate authentication, you might also want to disable that. This is because ssh prefers the certificate authentication algorithms, and if you connect to a host that offers a more preferred algorithm, ssh will try that and ignore the DNS. This is not very satisfactory; hopefully it will improve when the bug is fixed.

    HostKeyAlgorithms ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-rsa,ssh-dss

Troubleshooting

Check that your resolver is validating and getting a secure result for your host. Run the following command and check for "ad" in the flags. If it is not there then either your resolver is not validating, or /etc/resolv.conf is not pointing at the validating resolver.

    $ dig +dnssec <hostname> sshfp | grep flags
    ;; flags: qr rd ra ad; QUERY: 1, ANSWER: 3, AUTHORITY: 0, ADDITIONAL: 1
    ; EDNS: version: 0, flags: do; udp: 4096

See if ssh is seeing the AD bit. Use ssh -v and look for messages about secure or insecure fingerprints in the DNS. If you are getting secure answers via dig but ssh is not, perhaps you are missing "options edns0" from /etc/resolv.conf.

    debug1: found 6 secure fingerprints in DNS
    debug1: matching host key fingerprint found in DNS

Try using specific host key algorithms, to see if ssh is trying to authenticate a key which does not have an SSHFP record of the corresponding algorithm.

    $ ssh -o HostKeyAlgorithms=ssh-rsa <hostname>

Summary

What I use is essentially:

/etc/named/named.conf

    options {
        dnssec-validation auto;
        dnssec-lookaside auto;
    };

/etc/resolv.conf

    nameserver 127.0.0.1
    options edns0

/etc/ssh/ssh_config

    VerifyHostKeyDNS yes

Background on DNSSEC and non-validating stub resolvers

When ssh is not compiled to use ldns, it has to trust the recursive DNS server to validate SSHFP records, and it trusts that the connection to the recursive server is secure. To find out if an SSHFP record is securely validated, ssh looks at the AD bit in the DNS response header - AD stands for "authenticated data".

A resolver will not set the AD bit based on the security status of the answer unless the client asks for it. There are two ways to do that. The simple way (from the perspective of the DNS protocol) is to set the AD bit in the query, which gets you the AD bit in the reply without other side-effects. Unfortunately the standard resolver API makes it very hard to do this, so it is only simple in theory.

The other way is to add an EDNS0 OPT record to the query with the DO bit set - DO stands for "DNSSEC OK". This has a number of side-effects: EDNS0 allows large UDP packets which provide the extra space needed by DNSSEC, and DO makes the server send back the extra records required by DNSSEC such as RRSIGs.

Adding "options edns0" to /etc/resolv.conf only tells it to add the EDNS0 OPT record - it does not enable DNSSEC. However ssh itself observes whether EDNS0 is turned on, and if so also turns on the DO bit.

Regarding "options edns0" vs RRSET_FORCE_EDNS0

At first it might seem annoying that ssh makes you add "options edns0" to /etc/resolv.conf before it will ask for DNSSEC results. In fact on some systems, ssh is patched to add a DNS API flag called RRSET_FORCE_EDNS0 which forces EDNS0 and DO on, so that you do not need to explicitly configure the stub resolver. However although this seems more convenient, it is less safe.

If you are using the standard portable OpenSSH then you can safely set VerifyHostKeyDNS=yes, provided your stub resolver is configured correctly. The rule you must follow is to only add "options edns0" if /etc/resolv.conf is pointing at a local validating resolver. SSH is effectively treating "options edns0" as a signal that it can trust the resolver. If you keep this rule you can change your resolver configuration without having to reconfigure ssh too; it will automatically fall back to VerifyHostKeyDNS=ask when appropriate.

If you are using a version of ssh with the RRSET_FORCE_EDNS0 patch (such as Debian and Ubuntu) then it is sometimes NOT SAFE to set VerifyHostKeyDNS=yes. With this patch ssh has no way to tell if the resolver is trustworthy or if it should fall back to VerifyHostKeyDNS=ask; it will blindly trust a remote validating resolver, which leaves you vulnerable to MitM attacks. On these systems, if you reconfigure your resolver, you may also have to reconfigure ssh in order to remain safe.

Towards the end of February there was a discussion on an IETF list about stub resolvers and DNSSEC which revolved around exactly this question of how an app can tell if it is safe to trust the AD bit from the recursive DNS server.

One proposal was for the stub resolver to strip the AD bit in replies from untrusted servers, which (if it were implemented) would allow ssh to use the RRSET_FORCE_EDNS0 patch safely. However this proposal means you have to tell the resolver if the server is trusted, which might undo the patch's improved convenience. There are ways to avoid that, such as automatically trusting resolvers running on the local host, and perhaps having a separate configuration file listing trusted resolvers, e.g. those reachable over IPSEC.

On my toy nameserver my master zones are configured with a directory for each zone. In this directory is a "conf" file which is included by the nameserver's main configuration file; a "master" file containing the zone data in the raw binary format; a "journal" file recording changes to the zone from dynamic UPDATEs and re-signing; and DNSSEC and TSIG keys. The "conf" file looks something like this:

    zone dotat.at {
        type master;
        file "/zd/dotat.at/master";
        journal "/zd/dotat.at/journal";
        key-directory "/zd/dotat.at";
        masterfile-format raw;
        auto-dnssec maintain;
        update-policy local;
    };

I must have been having a fit of excessive tidyness when I was setting this up, because although it looks quite neat, the unusual file names cause some irritation - particularly for the journal. Some of the other BIND tools assume that journal filenames are the same as the master file with a .jnl extension.

I keep the name server configuration in git. This is a bit awkward because the configuration contains precious secrets (DNSSEC private keys), and the zone files are constantly-changing binary data. But it is useful for recording manual changes, since the zone files don't have comments explaining their contents. I don't make any effort to record the re-signing churn, though I commit it when making other changes.

To reduce the awkwardness I configured git to convert zone files to plain text when diffing them, so I had a more useful view of the repository. There are three parts to setting this up.

• Tell git that the zone files require a special diff driver, which I gave the name "bind-raw".

  All the zone files in the repository are called "master", so in the .gitattributes file at the top of the repository I have the line

      master diff=bind-raw
     

• The diff driver is part of the repository configuration. (Because the implementation of the driver is a command it isn't safe to set it up automatically in a repository clone, as is the case for .gitattributes settings, so it has to be configured separately.) So add the following lines to .git/config

      [diff "bind-raw"]
  	textconv = etc/raw-to-text
     

• The final part is the raw-to-text script, which lives in the repository.

This is where journal file names get irritating. You can convert a raw master file into the standard text format with named-compilezone, which has a -j option to read the zone's journal, but this assumes that the journal has the default file name with the .jnl extension. So it doesn't quite work in my setup.

(It also doesn't quite work on the University's name servers which have a directory for master files and a directory for journal files.)

So in September 2012 I patched BIND to add a -J option to named-compilezone for specifying the journal file name. I have a number of other small patches to my installation of BIND, and this one was very simple, so in it went. (It would have been much more sensible to change my nameserver configuration to go with the flow...)

The patch allowed me to write the raw-to-text script as follows. The script runs named-compilezone twice: the first time with a bogus zone name, which causes named-compilezone to choke with an error message. This helpfully contains the real zone name, which the script extracts then uses to invoke named-compilezone correctly.

    #!/bin/sh
    file="$*"
    command="named-compilezone -f raw -F text -J journal -o /dev/stdout"
    zone="$($command . "$file" 2>&1)"
    zone="${zone#*: }"
    zone="${zone%%:*}"
    $command "$zone" "$file" 2>/dev/null
  

I submitted the -J patch to the ISC and got a favourable response from Evan Hunt. At that time (16 months ago) BIND was at version 9.9.2; since this option was a new feature (and unimportant) it was added to the 9.10 branch. Wind forward 14 months to November 2013 and the first alpha release of 9.10 came out, with the -J option, so I was able to retire my patch. Woo! There will be a beta release of 9.10 in a few weeks.

In truth, you don't need BIND 9.10 to use this git trick, if you use the default journal file names. The key thing to make it simple is to give all your master files the same name, so that you don't have to list them all in your .gitattributes.

Imagine that...

Secure NTP is an easy-to-use and universally deployed protocol extension...

The NTP pool is dedicated to providing accurate time from anyone to everyone, securely...

NIST, creators of some of the world's best clocks and keepers of official time for the USA, decide that the NTP pool is an excellent project which they would like to help. They donatate machines and install them around the world and dedicate them to providing time as part of the NTP pool. Their generous funding allows them to become a large and particularly well-connected proportion of the pool.

In fact NIST is a sock-puppet of the NSA. Their time servers are modified so that they are as truthful and as accurate as possible to everyone, except those who the US government decides they do not like.

The NSA has set up a system dedicated to replay attacks. They cause occasional minor outages and screwups in various cryptographic systems - certificate authorities, DNS registries - which seem to be brief and benign when they happen, but no-one notices that the bogus invalid certificates and DNS records all have validity periods covering a particular point in time.

Now the NSA can perform a targeted attack, in which they persuade the victim to reboot, perhaps out of desperation because nothing works and they don't understand denial-of-service attacks. The victim's machine reboots, and it tries to get the time from the NTP pool. The NIST sock-puppet servers all lie to it. The victim's machine believes the time is in the NSA replay attack window. It trustingly fetches some crucial "software update" from a specially-provisioned malware server, which both its DNSSEC and X.509 PKIs say is absolutely kosher. It becomes comprehensively pwned by the NSA.

How can we provide the time in a way that is secure against this attack?

(Previously, previously)

I have done a little bit of work on nsdiff recently.

You can now explicitly manage your DNSKEY RRset, instead of leaving it to named. This is helpful when you are transferring a zone from one operator to another: you need to include the other operator's zone signing key in your DNSKEY RRset to ensure that validation works across the transfer.

There is now support for bump-in-the-wire signing, where nsdiff transfers the new version of the zone from a back-end hidden master server and pushes the updates to a signing server which feeds the public authoritative servers.

Get nsdiff from http://www-uxsup.csx.cam.ac.uk/~fanf2/hermes/conf/bind/bin/nsdiff

(Edit: I decided to simplify the -u option so updated from version 1.46 to 1.47.)

(Previously, previously, previously, previously, previously.)

We moved to new offices a month ago and I have settled in to the new route to work. Nico's nursery was a bit out of the way when I was working in the city centre, but now it is about a mile in the wrong direction.

But this is not so bad, since I have decided on a -Ofun route [1] which is almost entirely on cycle paths and very quiet roads, and the main on-road section has good cycle lanes (at least by UK standards). There is lots of park land, a bit of open country, and it goes through the world heritage site in the city centre :-) And it's fairly easy to stop off on the way if I need to get supplies.

[1] optimize for fun!

My route to work on gmap-pedometer

I don't have to wrangle children on the way home, so I take the direct route past the Institute of Astronomy and Greenwich House (where Rachel previously worked and where the Royal Greenwich Observatory was wound down).

My route home on gmap-pedometer

So far it has been pleasantly free of the adrenaline spikes I get from seeing murderous and/or suicidally stupid behaviour. Much better than going along Chesterton Lane and Madingley Road!

Bacon and brassicas are best friends. Here's a very simple recipe which is popular in the Finch household.

Ingredients

• A Savoy cabbage
• Two large or three small onions
• A few cloves of garlic
• A 200g pack of bacon
• Oil or butter for frying
• Soured cream

Prep

Chop the onion

Slice the cabbage to make strips about 1cm wide

Cut up the bacon to make lardons

Cook

Get a large pan that is big enough to hold all the cabbage. Heat the fat, press in the garlic, then bung in the onion and bacon. Fry over a moderate heat until the bacon is cooked.

Add the cabbage. Stir to mix everything together and keep stirring so it cooks evenly. As the cabbage cooks down and becomes more manageable you can put the heat right up to brown it slightly. Keep stir-frying until the thick ribby parts of the cabbage are soft as you like, usually several minutes. (I haven't timed it since I taste to decide when it is done...)

I serve this as a main dish with just a few dollops of sour cream on top and plenty of black pepper.

I'm annoyed by how slow our office printer is at printing on both sides of the paper. It occurs to me that it ought to be possible to make it much faster (a similar speed to single-sided printing) without too much extra complexity.

At the moment it handles one sheet at a time, in the sequence feed / print / reverse / print / eject. The feed and eject phases can be overlapped but there's otherwise little opportunity for pipelining.

If the duplex mechanism includes a paper path that goes from the print mechanism's exit to its entrance while turning over the sheet, then the path through the printer can be one-way (except inside the duplexer) and the duplexer can operate at the same time as the printer. The whole thing can then handle two sheets at once. The sequence goes like this:

• feed sheet 1
• print page 2 on sheet 1
• sheet 1 into duplexer / feed sheet 2
• sheet 1 through duplexer / print page 4 on sheet 2
• sheet 1 into printer / sheet 2 into duplexer
• print page 1 on sheet 1 / sheet 2 through duplexer
• sheet 1 exits / sheet 2 into printer
• print page 3 on sheet 2
• sheet 2 exits / feed sheet 3
• ...

I have assumed a C-shaped or S-shaped paper path, where the printer prints on the top of the sheet which turns over before dropping into the hopper, so that you end up with the stack of paper face down in the correct order. Our printer's duplex mode presumably prints pages in even/odd order (i.e. page 2 then page 1 on sheet 1, page 4 then page 3 on sheet 2, etc.) so the output stack still ends up in the right order. My duplexer's 2/4/1/3 page ordering puts greater demands on the RIPper's memory but that shouldn't be a big deal these days. (On the other hand, why does our printer appear to wait while RIPping? Shouldn't that be instant nowadays?)

So I wonder if anyone makes a printer with a duplexer that works this way. It should be fairly obvious from the duplex / duplex / exit / exit rhythm.

I hate plastic carrier bags, so I take a canvas bag when I go shopping (unless I forget). The city-centre Sainsbury's in Cambridge recently replaced their express tills with self-checkout tills, which use weighing scales under the bags to check that scanned things have been bagged properly.

If you put an unexpected object in the bagging area it flashes up an annoying message. This screen has a button on it saying "Using your own bag?" which I am pretty sure used to cancel the message and allow you to scan your shopping. It is now non-functional: if you try pressing it a member of staff has to come over and explain the correct procedure. If you want to use your own bag, before you put it on the bagging area you have to go into the "select an item" menu (for bananas and fresh bread etc.) and choose the "bag re-use" icon. Obviously.

The usual way to find an element in a sorted array is using a binary search, which takes log(n) time, where logs are understood to be in base 2 and N is the size of the array.

Linus Torvalds made the clever observation that you can do better than log(N) if you know that the contents of the array are uniformly distributed. For instance, git's pack files store multiple objects identified by the SHA-1 hashes of their contents. Each pack file has an index containing a list of the pack's SHA-1 IDs and their objects' locations in the pack. The index is sorted by SHA-1 ID. Since SHA-1 is a cryptographic hash, we can assume its output is uniformly distributed.

Linus described his technique as "Newton-Raphson" which is a bit of a misnomer, since N-R works on smooth differentiable curves whereas what we have is a straight line with some stochastic variations. What we're actually doing is an iterated linear interpolation. If the SHA-1 IDs were perfectly evenly distributed then a single linear interpolation would land us right on the target item, but the random variation means we will be off by some amount, so we need to continue searching.

How far off will we be? It turns out (based on Monte Carlo simulation) that the expected error is about 0.31 * sqrt(N) with a standard deviation of about 0.26 * sqrt(N). This is a really promising result since it implies that each iteration reduces the search space to N^1/2 whereas an iteration of binary search reduces it to N/2. So we should expect a complete search to take O(log(log(N))) iterations.

I wrote a simulation to try this out, and it matches this prediction: in fact the number of iterations was about 1 + log(log(N)). However what is the variation around this expected result? In my tests it turned out that the maximum number of probes was log(N) though for small N it bottomed out at about 16. When testing lots of different randomly filled arrays, the standard deviation was about 1.2 for all values of N, but when I tested fewer arrays this number ramped up.

Junio Hamano's implementation of Linus's idea is included in git but disabled by default. He added a tweak that biases the linear interpolation towards the centre of the search range, so it's kind of a balance between binary search and linear interpolation search. In my simulator this tweaked version required (log(N)+3)/2 iterations on average with a standard deviation of 0.8. The maximum number of iterations was again log(N) but it bottomed out at about 12. Overall it's a bit slower but better behaved.

In git, where a large repository might contain two million objects, and where pack index lookups are not particularly performance-critical, this improved lookup code doesn't provide a noticeable advantage. Still, I think it's interesting and the idea might be useful in other situations. Note that unlike a binary search, which can just use comparisons returning greater / equal / less, the linear interpolation search needs to know the absolute values of the elements. Git's code actually uses a lexicographic variant that ignores any common prefix shared by the elements in the search range, and uses only the next two bytes for the interpolation.

To finish, here's a bit of code. In this example, 0.0 <= array[k] < 1.0, and I use k for keys and v for values of array elements. We are searching for vtarg.

	/* all bounds are exclusive */
	double vlo = -DBL_MIN, vhi = +1.0;
	int klo = -1, khi = N;
	while(klo - khi > 1) {
		int kmid = klo + (khi-klo) * (vtarg-vlo) / (vhi-vlo);
		/* ensure rounding does not put us out of bounds */
		if(guess_k <= min_k) guess_k = min_k + 1;
		if(guess_k >= max_k) guess_k = max_k - 1;
		double vmid = array[kmid];
		if(vmid == vtarg) return(kmid);
		if(vmid < vtarg) klo = kmid, vlo = vmid;
		if(vmid > vtarg) khi = kmid, vhi = vmid;
	}
	return(-1);

Addendum: there are a few corrections in a follow-up post.

I've recently written a three page memo about the advantages of our username scheme compared to "friendly name" email addresses in large domains. I have put a copy of the PDF on the web which you can read if you like.

Here's an abbreviation to avoid, because its various meanings overlap so heavily.

• Source Code Manager: synonym for version control system, e.g. as used by the Linux crowd in the early days of git.
• Software Configuration Manager: usually incorporates version control, build system, archival of build products, and CASE methodology baggage, e.g. ClearCASE and Vesta.
• System Configuration Manager: for system administrators rather than developers, e.g. cfengine and Puppet.

I was originally planning to witter about distributed version control vs. centralized version control, especially the oft-neglected problem of breaking up a large cvs / svn / p4 repository. This was partly triggered by Linus's talk about git at Google in which he didn't really address a couple of questions about how to migrate a corporate source repository to distributed version control. But in the end I don't think I have any point other than the fairly well-known one that distributed version control systems work best when your systems are split into reasonably modestly-sized and self-contained modules, one per repository. Most systems are modular, even if all the modules are in one huge central repository, but the build and system integration parts can often get tightly coupled to the repository layout making it much harder to decentralize.

Instead I'm going to wave my hands a bit about the ways in which git has unusual approaches to distributed version control, and how bzr in particular seems to take diametrically opposing attitudes. I'm not saying one is objectively better than the other, because most of these issues are fairly philosophical and for practical purposes they are dominated by things like quality of implementation and documentation and support.

Bottom-up

Git's design is very bottom-up. Linus started by designing a repository structure that he thought would support his goals of performance, semantics, and features, and worked upwards from there. The upper levels, especially the user interface, were thought to be of secondary importance and something that could be worked on and improved further down the line. As a result it has a reputation for being very unfriendly to use, but that problem is pretty much gone now.

Other VCSs take a similar approach, for example hg is based on its revlog data structure, and darcs has its patch algebra. However bzr seems to be designed from the top down, starting with a user interface and a set of supported workflows, and viewing its repository format and performance characteristics as of secondary importance and something that can be improved further down the line. As a result it has a reputation for being very slow.

Amortization

Most VCSs have a fairly intricate repository format, and every operation that writes to the repository eagerly keeps it in the canonical efficient form. Git is unusual because its write operations add data to the repository in an unpacked form which makes writing cheaper but makes reading from the repository gradually less and less efficient - until you repack the repo in a separate heavy-weight operation to make reads faster again. (Git will do this automatically for you every so often.) The advantage of this is that the packed repository format isn't constrained by any need for incremental updates, so it can optimise for read performance at the expense of greater pack write complexity because this won't slow down common write operations. Bzr being the opposite of git seems to do a lot more up-front work when writing to its repository than other VCSs, e.g. to make annotation faster.

Thus git has two parallel repository formats, loose and packed. Other VCSs may have multiple repository formats, but only one at a time, and new formats are introduced to satisfy feature or performance requirements. Repository format changes are a pain and happily git's stabilized very early on - unlike bzr's.

Laziness

As well as being slack about how it writes to its repository, git is also slack about what it writes. There has been an inclination in recent VCSs towards richer kinds of changeset, with support for file copies and renames or even things like token renames in darcs. The bzr developers think this is vital. Git, on the other hand, doesn't bother storing that kind of information at all, and instead lazily calculates it when necessary. There are some good reasons for this, in particular that developers will often not bother to be explicit about rich change information, or the information might be lost when transmitting a patch, or the change might have come from a different VCS that doesn't encode the information. This implies that even VCSs that can represent renames still need to be able to infer them in some situations.

Git's data structure helps to make this efficient: it identifies files and directories by a hash of their contents, so if the hash is the same it doesn't need to look any closer to find differences because there aren't any - and this implies a copy or rename. This means that you should not rename or copy a file and modify it in the same commit, because that makes git's rename inference harder. Similarly if you rename a directory, don't modify any of its contents (including renames and permissions changes) in the same commit.

Mercurial also uses hashes to identify things, but they aren't pure content hashes: they include historical information, so they can't be used to identify files with the same contents but different histories. Thus efficiency forces hg to represent copies explicitly.

Any more?

I should say that I know very little about bzr, and nothing about tla, mtn, or bk, so if any of the above is off the mark or over-states git's weirdness, then please correct me in a comment!

We've been discussing configuration management in the office this week. None of us are happy with the way we're doing things...

On Hermes, we do most configuration management using rdist. On our management server we have a number of file trees containing files that differ from the default - a smattering of stuff in /etc, the contents of /home and /opt, and a few other bits scattered around. These trees are cloned and hacked for each flavour of machine (ppswitch, cyrus, lists, webmail, etc.) and each version of the underlying OS. These trees are mostly kept under revision control.

This setup has the advantage of simplicity, and it's easy to push out small changes. One key feature is rdist's testing mode, which makes it easy for us to ensure that the servers are in sync with the configuration tree without changing anything. We often run a test across a cluster of 10 or 16 machines in parallel. It's easy to selectively push a change to an idle machine for testing before rolling it out to the rest of the cluster. For more tricky changes I do a phased rollout so I can check for unwanted changes in behaviour without breaking the entire service at once.

Of course it has some serious disadvantages. We have to be root on the management host to be able to push changes out to the servers. We can't easily keep file ownership and permissions under revision control. This mechanism misses significant parts of the configuration, such as installed base OS packages and which rc scripts are enabled. There's also a lot of scope for improving our initial OS install scripts to reduce the amount that they get out of sync with the rdist configuration.

So we'd like something better. Our colleagues have different system management setups with different problems, and they are also looking for something better.

A couple of my colleagues have looked at Puppet but weren't happy with it. I dislike its basic design. Managed servers pull their configurations from the master, which means you must never screw up a change on the master, and it's harder to test changes - you have to explicitly set up test server profiles. Yes, you can run Puppet in push mode but it's often a bad idea to work against a program's basic architecture. Puppet also has its own security mechanisms, whereas I'd prefer to avoid multiplying channels of trust. Finally, I really hate writing configuration files for programs that write configuration files. It's a waste of brain cells to understand this superfluous abstraction layer: I just want to write the underlying configuration file directly.

Aside: this is why I really really hate autoyast, which uses an XML configuration file to control a program that writes configuration files that control rc scripts that manipulate the underlying configuration files for the programs you actually care about. It takes hours to work out how to make it produce the correct results.

I spent some time working on a program called pstx which was to be a suped-up replacement for rdist. It was going to be an sftp client (so it would require nothing special on the target servers) that had a simple configuration file to specify which directory trees to copy where, including ownerships and permissions (bringing them under revision control and removing the need to be root on the master), and possibly with added bells and whistles like remote diff, and a reverse (pull) mode. I also intended to make it easer to combine collections of files and thereby share common files. Sadly it's only about a third written and likely won't get much further.

One of the conversations this week was about how to reduce the chance of mistakes when rolling out changes, in which we discussed the use of revision control to help with testing and rollback. At the moment Hermes mostly uses CVS and other unixy bits of the CS share a Subversion repository, so the conversation very much assumed a central repository model - which fits in well with a master configuration server. Recently I have also been investigating git more seriously, so I thought it might be part of a solution.

The key things that git provides include a flexible and efficient network protocol for moving files around (flexible in that it can use ssh and http as well as git's native protocol, and efficient in that it's incremental and compressed), it can tell us what differs between a directory tree and the state of the repository, changes can be pushed and pulled, etc. The distributed version control functionality is way better at all this than pstx was ever going to be.

The big missing part is the ability to track ownerships and permissions: git only supports normal development checkouts which should be done using the developer's uid and umask. There are also some low-level problems with the way git performs checkouts: it removes the destination file before writing the updated version in its place. I would like a special deployment command which checks all the changed files out under temporary names, fixes their ownerships and permissions, then renames them into place. The first stage almost exists in the form of git-checkout-index --temp d, though it does weird things with symlinks. It doesn't look like much work to add the other stages.

This could provide some really nice workflows. A configuration change is created on a small topic branch, then pushed to the configuration repositories on all the machines - which changes none of the live configuration. You can then switch a test machine to the new branch with a single git deploy branch, or roll back by re-deploying the master branch. You can find out the current configuration of a machine in summary using git status or git diff to make sure the summary isn't a lie.

One interesting possibility might be to tame the clone-and-hack problem by using a shared repository for all the different classes of machines. This should make it easier to see the differences between each kind of machine and spot spurious ones.

One thing that is very manual in our current setup is hupping daemons to make them load an updated configuration. It might be feasible to use a post-deploy hook to do this, provided the hook script is given enough information that it can avoid unnecessary restarts.

Now I just need to find some time to turn the idea into code...

I posted a couple of articles (one, two) about the Corpus clock soon after it was unveiled, and I optained a copy of the Chronophage book soon after it became available. The book is a bit lacking in technical detail, so I was pleased to find out that John Taylor would be talking about it for the Cambridge Science Festival and I attended his talk yesterday. The lecture theatre was packed.

The talk was in three parts: a bit of autobiography, then a quick overview of the clock and its development, then questions. The talk revealed some interesting facts which do not appear in the book.

Taylor's story of how he came to make a fortune in kettle thermostats is relevant to the clock not just because that's how he made the money: his horological hero, John Harrison, invented the grasshopper escapement that inspired the Chronophage, and also invented the bimetal on which Taylor's thermostats rely. He explained his snap-action bimetallic disc, which has a C cut out to form a tongue in the middle; this tongue moves further than the centre of a disc without the cut-out does, which loosens the tolerances required to manufacture a thermostat. The calligraphic flourish engraved below his name on the clock's pendulum bob forms the shape of his bimetallic disc. (Sorry, I can't find a picture on line though it's visible in the book.)

ETA: I have found a large picture of the pendulum bob in which you can see the shape of Taylor's bimetallic disc under the date. It's overdrawn by some of the flourish so it's a bit obscure unless you know what you are looking for.

There were a couple of hints at the clock's workings. It is usual for clocks with chiming mechanisms to have a second set of drive springs or weights for the chimes. The Corpus clock has only one spring, so its hourly death-rattle is driven in an unusual way. This is why the clock ticks back and forth while rattling the chain in the coffin. There are two main mechanisms inside the Chronophage itself. It contains a mechanical pseudo-random mechanism to control the blinking and biting. The sting, however, is regular: it slowly rises then jabs down on each quarter hour.

He also mentioned that the clock "has fun" four times a year: on 24th March, which is the date of Harrison's birth and also his death; on 25th November, Taylor's birthday; on new year's eve and new year's day; and on Corpus Christi day, the Church's festival that occurs on the Thurdsday after Trinity Sunday, the 8th Sunday after Easter. The clock is away for maintenance this week, so I hope it'll be back in time to muck around on Tuesday week. The fun seems to involve even more erratic ticking than usual, with more colourful lights.

The clock's spring has to be particularly strong in order to overcome the momentum of the large escape wheel that goes around the outside of the clock. When prototyping the clock this caused a serious problem: the force of the spring is transmitted through the escapement to the pendulum, making it swing higher and higher and eventually breaking the clock. Taylor overcame this problem by adding a regulator, which also serves two other functions: it produces the clock's erratic behaviour that plays tricks with observers, and it listens to the MSF time signal to synchronize the clock every five minutes. (Taylor confirmed to me after the talk that these are all functions of the same mechanism. He also said that the hollow pendulum bob is not in fact "massive and weighty" as the book says, which answered my question about conservation of momentum.) I'm not sure how this is consistent with his assertions that the clock is purely mechanical - would it work if the computer regulator broke? News reports about the clock's teething problems suggest that it's pretty vital. I wonder if the maintenance periods this week and back in January are for software patches rather than mechanical adjustment?

I asked Taylor if he would publish more technical details about the clock, but he thinks that the mystery makes it fun. I disagree :-/

Since April 2002 I have been keeping a link log: a web page where I record links to other pages that are notable in some way, with a brief comment about each one. It's gatewayed to Delicious, LiveJournal, and Twitter. The Twitter feed is new.

I've been on Twitter since March 2007, when it made a big splash at the SXSW festival. I joined to see what the fuss was about but soon stopped using it. None of my social circle were using it much, and there wasn't a sensible way of finding people in the more distant reaches of my social network. For 18 months my last tweet said " Grumbling about the difficulty of finding out people's twitter usernames".

Recently Twitter has taken off in the UK, since a fairly large contingent of journalists and celebrities have started using it and talking about it. (Reminds me in a small way of the rise of the web in 1993/4.) Coincidentally at about the same time I decided to get back into using Facebook and Twitter a bit more, to keep in better touch with my family's activities. (They're on Facebook but I linked my Twitter and Facebook statuses together for convenience.)

The celebrity thing helped me to get more out of Twitter in a significant way. I had thought of it as more like Facebook or LiveJournal: a way of keeping up with the activities of people I already know. But in fact it's more like the wider blogging culture where it's normal to follow someone's writing just because they are interesting. (Yes, LJ blurs into this kind of blogging too.) In fact the even the Twitter guys didn't realise this at first: until June 2007 Twitter sent me email saying "You are foo's newest friend!" but the following month it started sending me email saying "foo is now following you on Twitter!". I now feel free to follow well-known people just because they are interesting, and I found more interesting people by looking through the lists of people they follow.

Part of the Twitter culture is heavy use of short URL services when posting interesting links. I decided that my link log ought to be gatewayed to Twitter to join in the fun, so I embarked on a bit of hacking. Previously it had been just a static HTML page, with a command-line script that I used to insert a new link. There was another script to turn the HTML into an RSS feed for LJ, and some code for uploading the results to chiark. I had a rudimentary click tracker so that I could get some idea of what links other people followed, but it did not shorten URLs. (That meant it was an open redirector until I found out what evil that made it vulnerable to.)

I replaced all the old static HTML and RSS gubbins with a CGI script which can format my link log in HTML or Atom, as well as providing short URLs for all the links. I decidided to host my own short URLs partly to continue tracking what people find interesting, and partly because I have a vanity domain that's just right for this job :-) The command line script for adding new links remained basically the same, apart from new code to create short tags and to post the link to Twitter.

After a couple of weeks of this new regime I decided I needed to be able to save links found when reading Twitter or LiveJournal on my iPod Touch. Its UI makes it easy to email links but not much else, so I set up a gateway from email to my link log. I send links to a specially tagged email address which is filtered to a special mailbox. A script polls this mailbox over IMAP every few minutes, looking for messages that match a number of paranoid checks. From these extracts a URL and a comment which it passes on to the old command-line script. (I still use the latter when I'm on a computer with a keyboard.)

The end result is pretty neat: I can easily save interesting links that I see in places where that was not previously practical. It's probably a good thing I don't have an iPhone because then I'd be able to spod everywhere.

PS. a brief hate: web sites that redirect deep links to the mobile version of their front page. Utter cWAP. They'll get no Google Juice from me. (In fact the iPhone browser is good enough that mobile sites are usually NOT an improvement.)

The Student Loan Company executive management board minutes from a meeting just over a year ago says the following in section 6, "update on data security processes":

RSJ provided an update on Data Security and advised that information which was being received from external sources confirmed that the transfer of data on removable media devices was now unacceptable. He stated that there was a need to consult with HEI’s as to the method of transferring Attendance Confirmation Reports as SLC now had PGP encryption software available which could replace the previous method of transferring the data via CD’s. He also stated that the PGP software which SLC were using should be checked to ensure that it was on the US Government list of standard encryption as HEI’s are only permitted to use PGP software from this list.

Not shipping media is good. Using end-to-end encryption is good. (Unlike banks which seem to like SMTP over TLS, which provides no additional security for inter-domain communication.) I wonder why the choice of PGP instead of S/MIME - I believe that PGP usually requires an add-on whereas S/MIME is often built in to MUAs. Perhaps they've been nobbled by a vendor.

In 2005 I developed a mathematical model for measuring average event rates which became the core of a new rate limiting feature for Exim. The model has a particularly useful property which I did not expect it to have and which I did not (until recently) fully understand.

The model

The central formula is the standard exponentially weighted moving average:

r_new = (1 − a) ∗ r_inst + a ∗ r_old

We use this to calculate the new average rate from the instantaneous rate and the result of the previous average calculation. These rates are all measured in events per some configurable time period. The smoothing factor a is a value between 0 and 1 which determines how slowly the model forgets about past behaviour.

We calculate r_inst and a from the raw inputs to the formula, which are p, a time period configured by the postmaster, and i, the time interval between the previous event and this event. By dividing them we get

r_inst = p / i

In this formula, p determines the per time unit used for measuring rates, e.g. events per hour or events per day.

The exponentially weighted moving average is usually used to smooth samples that are measured at fixed intervals, in which case the smoothing factor, a, is also fixed. In our situation events occur at varying intervals, so the smoothing factor needs to be varied accordingly.

a = e^{−i / p}

In this formula, p determines the smoothing period, i.e. the length of time it takes to forget 63% of past behaviour.

A useful property

When developing the model, I needed to understand how it reacts to changes in the rate of events. It's fairly simple to see that if the rate drops, the average decays exponentially towards the new rate. It's less clear what happens when the rate increases. A particular practical question is what happens if there's a sudden burst of messages? How much of the burst gets through before the average rate passes some configured maximum?

I did some trial computations and I found that when the interval is very small (i.e. the rate is high) the average rate increases by nearly one for each event (the smaller the interval, the closer to one). This means that the maximum rate is also the maximum burst size. How wonderfully simple! The postmaster can configure the model with two numbers, a maximum number of events per a time period, which also directly specifies the units of measurement, the smoothing period, and the maximum burst size.

(The maximum burst size is larger for slower senders, increasing to infinity for those sending below the maximum rate. However you don't have to be much above the maximum for your average to hit the limit within one period.)

This property produces a simple user interface, but I did not understand how it works. It's obvious that when i is small, a ≈ 1, but it is not so clear why (1 − a) ∗ r_inst ≈ 1. It seems I landed directly on a mathematical sweet spot without the fumbling around that might have led me to understand the situation better.

Arbitrary choices

I made two choices when developing the model which at the time seemed arbitrary, but which both must be right to get the max rate = burst size property.

Firstly, I decided to re-use the configured period for two purposes: as the smoothing period and as the per time unit of rates. I could instead have made them independently configurable, but this seemed to give no benefits that compensated for the extra complexity. Alternatively, I could have used a fixed value instead of p in the formula for r_inst, but that seemed liable to be confusing or awkward, and to require more mental arithmetic to configure.

Secondly, I decided to use e as the base of the exponent. I could have used 2, in which case the smoothing period would have been a half life, or 10, so that 90% of past behaviour would be forgotten after one period. There seemed to be no clear way to choose, so I split the difference and went with e on the basis of mathematical superstition and because exp() has fewer arguments than pow().

How it works

Looking back over my old notes this week, I had a revelation that the max rate = burst size property comes from the fact that the gradient of e^x is 1 when x is 0. To show why this is so, I first need to define a bit of notation:

y ≡ f(x) ≡ e^x

δy ≡ f(x + δx) − f(x)

δx ≡ −i / p

This allows us to say, when x is zero and δx is small,

	(1 − a) ∗ rinst
=	(1 − e−i/p) ∗ p/i
=	(1 − eδx) / −δx
=	(eδx − 1) / δx
=	(e0 + δx − e0) / δx
=	( f(0 + δx) − f(0) ) / δx
=	δy / δx
≈	dy / dx
=	ex
=	1

Sweet.

One notable feature of the ports on the new MacBook is that the RJ45 Ethernet socket only just fits - it wouldn't if the machine were much thinner. In fact the MacBook Air notoriously doesn't have any wired ethernet connection at all, relying on IEEE 802.11n WiFi for connectivity.

Of course other manufacturers are making expensive thin laptops. The Dell Adamo neatly solves the RJ45 thickness problem by putting the port behind the display hinge, where the machine is as thick as the body plus the display.

The Voodoo Envy's solution is to put the ethernet socket in the power supply, which acts as a WiFi hot spot which the laptop uses for connectivity. This is cute but it means you only get 54Mb/s because the base station doesn't have 802.11n support.

A cheaper and faster alternative would be to pass a gigabit Ethernet connection through from an RJ45 on the power supply to a combined power network port on the laptop. The connector could be much thinner than RJ45 without sacrificing compatibility.

ETA: The other advantage this design would have is that the combined power and ethernet connector can use the magsafe idea, so you don't have the problem of one safe and one unsafe connector when tethered.

I'm happy to say that the problem I ranted about in my previous entry has been fixed. The general guidelines for bulk email have been restored, and the new guidelines for intraspam large internal mailing lists have been published on their own page.

This afternoon my colleague Andy gave a talk about Microsoft Exchange 2007, which I attended since I need to know what the competition has to offer and I have to provide support for its SMTP interfaces. One thing he mentioned which perked up my interest was "autodiscovery" for Outlook 2007. The unnecessary difficulty of configuring email software has irritated me for a long time, so after the talk I immediately went to find out more. It turns out to be a mixture of good stuff and utter FAIL.

The documentation describes three ways that Outlook 2007 can configure user accounts automatically - server names, security requirements, etc. If you are logged into a Windows Domain then it first tries querying the Active Directory. If that succeeds then it can find everything out by itself. Nice. If not, it falls back to an open protocol, which any standards-based mail server can implement, that configures the server settings automatically given an email address. More about this below.

If server-supported autodiscovery doesn't work, Outlook tries to guess the settings by attempting various combinations of host name, port number, TLS or not, POP or IMAP, etc. and stopping when it finds something that works. I think this is a great idea, so it's a damn shame that it prefers to use the lame POP not the studly IMAP if both are available. By itself that is enough to make it worth our while to implement the autodiscover protocol; but because our primary mail domain is cam.ac.uk but our service name is hermes.cam.ac.uk, Outlook's guesses will fail. This has the advantage of preventing users walking blindly into bad configurations, but the disadvantage that they're less likely to be able to configure it at all.

And so to the autodiscovery protocol itself. How can something so simple be fucked up in so many ways? It looks to me like it was bodged together by a clueless intern over two or three summer breaks, each time getting worse as the requirements evolved. The result is a case study in what RESTful protocol design is not.

The essence is simple: the client sends a request containing the user's email address, and the server sends back an XML document containing the configuration settings. The request is sent using HTTP-over-SSL to a URL derived from the domain part of the user's email address. (In fact it tries https://domain/autodiscover/autodiscover.xml first, then tries https://autodiscover.domain/autodiscover/autodiscover.xml.) So far, so good.

The first mistake is that the request is a POST with the email address contained in another XML document in the request body. It would have been more RESTful to use a GET with the email address encoded in the URL. This mistake turns into FAIL when you realise that most email services have the same settings for all users, in which case autodiscover.xml can be a static file, but many web servers do not allow POST requests to static files. If they had done it right, using a GET request with the email address in the query string would have Just Worked for both CGI scripts and static files.

It gets worse when they bodge around this mistake. A POST to a file commonly results in a "405 Method Not Allowed" error. Microsoft specify that if this is the case for your web server, you should configure it to send the autodiscover.xml file in the error reply, as if the request was successful. A foul perversion of the protocol.

It gets worse when they add support for virtual domains. The requirement seems to be that the service provider wants to host the autodiscover.xml script centrally, and doesn't want to fork out for an SSL certificate for every virtual domain. So if both of the https URLs fail, Outlook tries a GET request to the autodiscover.domain URL, which can redirect to the central autodiscover.xml. However that's not secure enough so there must also be an _autodiscover._tcp.domain SRV record in the DNS pointing to the same central web server. However that's still not secure enough so Outlook also admonishes the user to click OK in a popup dialogue box.

It gets worse when you look at the autodiscover.xml "schema". It isn't a schema, it's a commented skeleton fill-in-the-blanks autodiscover.xml file. That's just everyday lameness; the real FAIL is to be found in the various elements described therein. The redirect I mentioned above isn't an HTTP redirect, it's an autodiscover.xml document containing various redirection settings. There are also settings for controlling the expiry time of the document, because of course configuring these in a .htaccess file is too hard.

Ugh. I think that just about exhausts the rantage this stuff has triggered. I am most of the way to implementing it; I just need to get the necessary SSL certificates. It turns out to be easier than I expected because newish Apache does not get upset by POST requests aimed at static files: it just throws away the request body and returns the file with a "200 OK". No need to fart around with ErrorDocument 405 autodiscover.xml. With any luck it'll make Outlook trivial to get to work with Hermes.

• I said the clock has three circles of 60 slits. In fact it has two circles of 60 and one of 48 - the hour circle has a slit for every quarter hour.
• A website about the clock is going live soon.
• A book about the clock is being published, and it will be available from the Corpus Christi porters' lodge amongst other places.

Turning a linear day number into a date is about twice as difficult as the reverse calculation, both from the computer's point of view and the programmer's. The overview of the function is to (1a) calculate the year (1b) subtract the day count for previous years (2a) calculate the month (2b) subtract the day count for previous months. These pairs of operations are essentially calculating quotients and remainders to produce successive components of the dates.

The trickiest part is dealing with the Gregorian correction. You can work out the Julian year in which a day number occurs using d*4/1461 which is a straight-forward inverse of the corresponding part of the reverse calculation (though you need to fiddle with the epoch to make the leap years fall in the right place). The equivalent for the Gregorian calendar, dividing by the average length of a year using integer arithmetic, is d*400/146097. However this produces leap year intervals of 4 or 5 years, not 4 or 8 years. Fortunately the book describes a neat trick which allows us to use this formula to estimate the day's year, then adjust it to fix any error.

Errors are detected using the forwards conversion from years to day numbers, y*1461/4 - y/100 + y/400. This formula produces the number of days from the start of 1 A.D. up to the end of year y inclusive, according to the conventional numbering. My code internally adjusts the year to start with March instead of January; the formula works for adjustments like this so long as the numbering of February doesn't change. (Note that the formula in my earlier post adjusts the year number so that it refers to the end of the previous February, to which is added a day count corresponding to the fraction of the current year that has passed.)

So what we do is calculate d*400/146097 and add one to estimate the year according to the conventional numbering. The result is always an underestimate (i.e. the formula guesses that years start up to two days late) so we may in fact get the previous year's number. We calculate the count of days up to the end of the estimated year and compare with the original day number. The original day number should normally be before the calculated end of the year. If the estimate was wrong, we need to increment the year number again.

We then need to obtain the remainder of days within this year by subtracting the day count up to the end of the previous year. To get this count we subtract one from the year and do the forward calculation again. If we combine the decrement with the estimate correction, the resulting code looks like this, where dn is day number and dy is day of year.

	y = dn*400/146097 + 1;
	y += (dn >= y*1461/4 - y/100 + y/400) - 1;
	dy = dn - y*1461/4 + y/100 - y/400;

The month calculation is more awkward than I would like because of a mismatch between the forward m*153/5 and reverse dy*5/153 rounding patterns, as I've illustrated below. In each column I've italicised the five-month cycle that corresponds to March - July.

The result is that the code needs a series of different administrative fiddles to work out the month and the day of the month. First add one month of days to line up with the italic part of the reverse pattern, then calculate the month giving March = 1 through to February = 12. Then add three months to line up with the italic part of the forward pattern, March = 4 to February = 15, and calculate the number of days before the month. Subtract this from the day of the year, then add four months of days to compensate for the fiddles, to finally get the day of the month.

	m = (dy + 31)*5/153 + 3;
	d = dy - m*153/5 + 123;

The last step is to restore the year to its usual January - December alignment. This, at least, is a simple inverse of the corresponding code in the forwards direction. There's also a preparatory adjustment of 10 months at the start of the code to set up the March - February alignment in the first place. After a few tweaks, the final code is:

void F(int d, int *py, int *pm, int *pd) {
	int y, m;
	d += 305;
	y = d*400/146097 + 1;
	y -= y*1461/4 - y/100 + y/400 > d;
	d -= y*1461/4 - y/100 + y/400 - 31;
	m = d*5/153 + 3;
	d -= m*153/5 - 92;
	if (m < 14) m -= 1;
	else m -= 13, y += 1;
	*py = y, *pm = m, *pd = d;
}

• 305 is 10 months (March - December) minus the epoch (1st January 1 A.D. is day 1)
• 400 is the number of years in a Gregorian cycle and 146097 is the number of days
• 1461 is the number of days in 4 years, usually
• 153 is the number of days in 5 consecutive months, except February
• 31 is one month of days to align the reverse month calculation, from 31*5/153 == 1
• 3 aligns the forward month calculation
• 92 is three months of days to compensate for the three months added in the previous line, from 3*153/5 plus an extra one because we count days within a month from 1 not 0
• actually 92 = 4*153/5 - 31 + 1 where the extra 31 is the same 31 we added previously

Edited to add...

It's possible to make the forward and reverse patterns line up by adjusting the 153/5 factors, which saves a couple of additions. The smallest denominator for which this works is 17, which produces the following code. Before the final fix-up, months are numbered Mar=1 - Feb=12.

void G(int d, int *py, int *pm, int *pd) {
	int y, m;
	d += 305;
	y = d*400/146097 + 1;
	y -= y*1461/4 - y/100 + y/400 > d;
	d -= y*1461/4 - y/100 + y/400 - 31;
	m = d*17/520;
	d -= m*520/17;
	if (m < 11) m += 2;
	else m -= 10, y += 1;
	*py = y, *pm = m, *pd = d;
}