Forem: Dave Cridland

It's always DNS

Dave Cridland — Sun, 09 Nov 2025 13:48:57 +0000

It is always DNS... Sometimes

It might seem as if the DNS, or the "Domain Name System", is highly unreliable. A major AWS outage was traced to an incorrectly set-up DNS entry, and the old hands (and new hands) in the industry all smiled knowingly and said "it's always DNS", even though it was really the DynamoDB global table names, the DNS was working perfectly, and nobody else would have been using that DNS entry directly.

The DNS isn't really the cause of many outages and problems - but it is involved in lots of them, and has privacy leaks and performance issues. And this is because it is usually so reliable we use it for literally everything, and use it with an intensity that results in us pouring information into it as well as relying totally on the information we get back.

In this post, I'll explain why we have the DNS, how it works, how to make it faster, and how to make it more private. And how it goes wrong.

And also I'll prove, beyond a shadow of a doubt, that my servers are faster than Google's.

A Gentleman's Primer In DNS

So let's remind ourselves about the Domain Name System. The Internet operates on addresses - originally NCP, then IPv4, and then more recently, often IPv6. These are magic numbers - we tend to think of IPv4 addresses as four 8-bit numbers, but really it's a single 32-bit number, and IPv6 addresses are a giant 128-bit number. But thanks to Vint Cerf's epiphany on the back of a napkin, they're split at multiple points to form subnet addresses, which makes routing - the decision of where to send the packets - really easy (and fast!).

Many of us probably remember half a dozen IPv4 addresses without thinking. We're in the habit of typing 127.0.0.1 instead of localhost, and these days having to train ourselves the other way lest we miss out on ::1, the IPv6 version. If you've a static IPv4 address from your ISP, you might memorize that.

But you probably don't memorise all the possible IP addresses for Google, for example - instead you want to type www.google.com and get back the address.

This was originally solved on the Internet by the simple method of having a text file containing the names and their addresses, and sharing this around via email or whatever. Convenient, but it turns out this didn't scale well - though it still exists as /etc/hosts on UNIX systems as a fallback.

And, moreover, you might want to know more than just the address - you might want to know how to send email there, or where the XMPP server is, or what settings to use for TLS, and so on - making a single text file get fairly complicated.

What we needed was a distributed database.

A Lady's Primer in the DNS

First things first: because it's "The Domain Name System", real experts call it "The DNS". Top tip to make yourself look like you know what you're talking about, that.

Domain names are a sequence of labels, each followed by a dot. Each label is - normally - lower case alphanumeric characters, plus '-'. Note that at a low level, the DNS never handles Unicode, but from a purely technical standpoint, it can have labels with anything at all in (including, wildly, dots and spaces).

The DNS has the concept of a "zone" - something you might normally call a "domain", though it's slightly different. Zones contain records - the only mandatory records are the "Start Of Authority" (SOA) record, which lists settings for the zone, and the "Name Server" (NS) records, which list the nameservers. Those are given as fully qualified domain names themselves, which does give us an interesting chicken and egg problem. These records will have a key which will be the same domain name as the name of the zone.

NS records with a different domain name essentially state that the listed nameservers will answer queries for this other domain (as another zone).

A and AAAA records list the IPv4 and IPv6 addresses for the label. There's other record types too - I'm going to skip over them, but they're often quite important.

To query the DNS from first principles, you'll need a list of the Root Servers. We can get one just by using dig, like this:

dig . NS

This is asking for the nameservers for the domain name ".". Remember I said it was labels followed by a dot? Google's domain is really "google.com.", but we skip the last dot usually. Putting it there - on some programs at least - tells the program not to look on our local domains.

The response will be something like:

; <<>> DiG 9.18.39-0ubuntu0.24.04.2-Ubuntu <<>> . NS
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 54773
;; flags: qr rd ra; QUERY: 1, ANSWER: 13, AUTHORITY: 0, ADDITIONAL: 27

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 65494
;; QUESTION SECTION:
;.              IN  NS

;; ANSWER SECTION:
.           309030  IN  NS  e.root-servers.net.
.           309030  IN  NS  h.root-servers.net.
.           309030  IN  NS  a.root-servers.net.
.           309030  IN  NS  j.root-servers.net.
.           309030  IN  NS  b.root-servers.net.
.           309030  IN  NS  l.root-servers.net.
.           309030  IN  NS  c.root-servers.net.
.           309030  IN  NS  g.root-servers.net.
.           309030  IN  NS  d.root-servers.net.
.           309030  IN  NS  f.root-servers.net.
.           309030  IN  NS  k.root-servers.net.
.           309030  IN  NS  i.root-servers.net.
.           309030  IN  NS  m.root-servers.net.

;; ADDITIONAL SECTION:
a.root-servers.net. 309030  IN  A   198.41.0.4
b.root-servers.net. 309030  IN  A   170.247.170.2
c.root-servers.net. 309030  IN  A   192.33.4.12
d.root-servers.net. 309030  IN  A   199.7.91.13
e.root-servers.net. 309030  IN  A   192.203.230.10
f.root-servers.net. 309030  IN  A   192.5.5.241
g.root-servers.net. 309030  IN  A   192.112.36.4
h.root-servers.net. 309030  IN  A   198.97.190.53
i.root-servers.net. 309030  IN  A   192.36.148.17
j.root-servers.net. 309030  IN  A   192.58.128.30
k.root-servers.net. 309030  IN  A   193.0.14.129
l.root-servers.net. 309030  IN  A   199.7.83.42
m.root-servers.net. 309030  IN  A   202.12.27.33
a.root-servers.net. 309030  IN  AAAA    2001:503:ba3e::2:30
b.root-servers.net. 309030  IN  AAAA    2801:1b8:10::b
c.root-servers.net. 309030  IN  AAAA    2001:500:2::c
d.root-servers.net. 309030  IN  AAAA    2001:500:2d::d
e.root-servers.net. 309030  IN  AAAA    2001:500:a8::e
f.root-servers.net. 309030  IN  AAAA    2001:500:2f::f
g.root-servers.net. 309030  IN  AAAA    2001:500:12::d0d
h.root-servers.net. 309030  IN  AAAA    2001:500:1::53
i.root-servers.net. 309030  IN  AAAA    2001:7fe::53
j.root-servers.net. 309030  IN  AAAA    2001:503:c27::2:30
k.root-servers.net. 309030  IN  AAAA    2001:7fd::1
l.root-servers.net. 309030  IN  AAAA    2001:500:9f::42
m.root-servers.net. 309030  IN  AAAA    2001:dc3::35

;; Query time: 5 msec
;; SERVER: 127.0.0.53#53(127.0.0.53) (UDP)
;; WHEN: Sat Nov 08 17:14:21 GMT 2025
;; MSG SIZE  rcvd: 811

The actual answer to what we asked is in the "Answer Section" - which is fair enough, really. It tells us that there's a set of Root Servers numbered - okay, lettered - from a to m. You'll notice that in the answer, they're jumbled up - they're all equal, and if a were always listed first, it'd risk getting all the traffic.

However, since this just gives us domain names, and we need to use the DNS to look those up, this would be fairly useless - so instead of just that, it gives us "Additional" records which it thinks we will find useful. This includes all the address records, in this case, which is just as well. These are called "Glue Records", and are usually very helpful. And that, right there, was dramatic foreshadowing, that was.

Glue Records are needed because the only way to look up x.root-servers.net. A would be by knowing where root-servers.net. NS was, and we don't know that without knowing the addresses for the root servers to ask where to find net. NS.

You can't just ask the root servers to look everything up for you, though, because there's two kinds of DNS server.

Authoritative Servers actually hold the data for a particular zone - the Root Servers are the Authoritative Servers for ".". They will typically only provide answers for the zone they're authoritative for. (There might be a "primary" and several "secondaries" for a zone, but that's a detail that doesn't matter to us - they're all authoritative and you can't tell where the data is actually sourced from).

Recursive Servers (also known as Resolvers) don't hold authoritative data at all, they're just there to make our lives easier and faster. These will have that list above statically stored - remember that before the DNS, we had to share text files with all the servers' names in? Now we just share the root server list around. It's not as big.

However, Authoritative Servers do answer queries for subdomains (or "delegated zones"), at least by handing over the NS records of the delegated zone.

So when we type:

dig www.google.com. A +aaonly +norecurse @<ip address for root server>

... we get back the servers not for Google, but for "com.". We can then pick one of those, and ask again, and we'll get Google's nameservers (via a Glue Record in "com.", by the way), and finally, by asking them, we'll get our address.

(Asides: Why did I elide the IP address there, despite listing them all above? Because nobody wants every person reading this to hit the same root server. No really. Why did I include the + flags? To stop the root server operating in recursive mode - which it won't, but it might cause additional logging for those folks running them. Why am I querying for an IPv4 record over IPv6? Well, no reason, really.)

dig www.google.com +aaonly +norecurse A @2001:4860:4802:34::a

.. fill finally give us:

;; QUESTION SECTION:
;www.google.com.            IN  A

;; ANSWER SECTION:
www.google.com.     300 IN  A   142.250.140.105
www.google.com.     300 IN  A   142.250.140.147
www.google.com.     300 IN  A   142.250.140.106
www.google.com.     300 IN  A   142.250.140.99
www.google.com.     300 IN  A   142.250.140.104
www.google.com.     300 IN  A   142.250.140.103

;; Query time: 37 msec

And that's all great whelp it takes 37ms for each query and how many queries?

This is too slow.

Cache and Carry

Cache and Grab

Recursive nameservers do two things for us - they'll handle the multiple queries so we only need to do one, and they'll also cache the request for us too.

The numbers (300 in the last response) tell us the "Time To Live", or "TTL", on the record. Google is telling me that I can cache this one for 300 seconds (5 minutes). Since all the records have this, I can drop the number of queries down to, well, none.

Our client machine can also cache, but typically a recursive resolver runs at your ISP, and will cache for all its customers.

This means the DNS can be really much faster. My ISP will return the result in (typically) 18-20ms, because it'll be fully cached. If it isn't, it'll take closer to 27-30ms.

These are so useful that they're part of the connection data you'll get as you connect. Your phone or laptop uses DHCP; your router will get the same via PPP options. Finding your local resolver means getting a faster DNS service - and thus a faster connection.

Cache is King

To make things even faster, you can (remarkably easily) run your own recursive nameserver at home, on a Raspberry Pi or similar. I run two, in fact, on "real" Linux machines, because I am perfectly normal and in no way stupidly nerdy. These will return me answer (cached, of course) in about 1-2ms.

If only we could measure this over months and have graphs. (I do. Of course I do).

Here's my ISP's DNS server (or one of them), for the past 10 days:

And here's mine:

And for comparison here's Google's 8.8.8.8 public DNS resolvers:

I include this as definitive proof that my servers are faster than Google's, incidentally. Honestly, sometimes I'm such a genius I even impress myself.

Speed, Reliability, and Privacy

Almost every connection to any service will involve, as a first step, a DNS lookup. In fact, the only exception I can think of is the DNS root server queries themselves.

That means - quite obviously - speed is crucial. That 20 (or 2) millisecond DNS tax is paid for every single connection.

It means reliability is crucial. If the DNS fails, then of course the connection cannot continue.

And DNS can fail - of course it can - in numerous ways.

How can I fail thee? Let me count the ways

Bad Answers

It goes without saying - but I'll say it anyway of course - that if the data in the authoritative DNS servers is wrong, you'll get wrong answers, and things won't work.

If a lookup for www.google.com. gave me the IPv4 address of 127.0.0.1, it's going to be game over. This is the kind of failure that brought down AWS, incidentally - everything worked perfectly, but the wrong DNS records were put in, and thus the wrong ones came out.

Obviously "It's always DNS" applies here, but really, it was Terraform or Cloud Formation or something.

A more common case is where the service is intentionally moving, and the caching of DNS records causes resolvers to provide the old address. (Fix: lower TTLs the day before a move!)

Bad Glue

Oh, wait, I foreshadowed this! I hope you were paying attention.

Glue Records are vital for locating nameservers when the nameservers' names are in the zone they're serving. But - and you'll like this pun, I promise - when glue records are missing or incorrect, things can come unstuck.

A classic case is where a nameserver moves address - this is so rare that the precise things needed are sometimes forgotten, like not only updating the authoritative records but the glue as well.

Suddenly the entire zone drops offline - but only for those resolvers using the wrong glue address.

It's maddeningly difficult to diagnose such cases because any resolver with the NS records cached might never see the problem, only "new" traffic will fail, and even then perhaps only half of it.

DNS Server Offline

Obviously if there's no DNS server listening at the right IP address, you won't get a response. DNS operates (at least usually) over UDP, so packets get lost, and we have to retry. If nothing's there we'll retry a lot.

Even if the server is present, but the link is lossy, this can add a substantial amount of time to the lookup - and that will add up surprisingly quickly into a delay that an actual human will notice as being "a slow site".

"Lame" Delegation

Maybe there is a server that responds, but maybe it says it's not the authoritative server the parent said it was? These are known as "Lame" delegations, and might be down to bad answers in the parent, or bad glue.

And Privacy?

Privacy is a bigger problem than just the DNS, but DNS servers are a key part of the problem.

If every site you visit gets looked up in DNS, then the DNS server you're using gets every site you visit.

When that's your ISP (at least in sane jurisdictions), that's most likely fine. You have a contract with your ISP, and in most sane jurisdictions they'd have to tell you, at least, if they were gathering the data (and generally they'd have to ask your permission).

But if it's a rando WiFi in a café? Yeah, they should still ask, but honestly, who knows?

DoT and DoH

DoT, or DNS over TLS, allows you to directly use a particular DNS provider over a TLS encrypted connection. This is good for privacy, but comes with a cost - the provider isn't local to you, and will be slower.

DoH is much the same, but uses HTTPS rather than simply running the DNS protocol directly over TLS - it's useful for cases where other protocols may be blocked at the firewall, or where you want to minimize the likelihood that someone can tell it's DNS traffic rather than just another website (but they can tell anyway).

There are privacy-focused providers, such as Quad9, and there's also Google. As ever, encryption doesn't solve problems, it just moves them, and a DoT/DoH provider like Quad9 or Google could choose to log all your queries just like a nefarious café owner.

At home, you're likely paying a "tax" of around 5ms for using these by my measurements - so I'd recommend not to bother unless you genuinely cannot trust your ISP. But when out of the house, you probably want to, so they're worth considering for mobile devices and laptops you use on arbitrary WiFis.

I do not understand why ISPs don't offer DoT, DoH, and indeed full-blown VPN access for their customers. If you're an ISP reading this, this is a free product idea and I'd love you to do it.

DNSSEC

A parallel security issue with the DNS (in general, but particularly problematic in rando WiFi situations) is that the operator of a DNS service - whether or not it's using TLS - can simply fake the answers, redirecting you to a site under their control.

Assuming you're using TLS (usually via HTTPS) this isn't as big a problem as you'd think, surprisingly, but they can generate a lot of confusion. And if a Certificate Authority gets duped into handing out a certificate, it becomes a nasty issue.

DNSSEC allows each individual record to be signed, which means that even when the records are cached, they're still trustworthy.

HTTPS

HTTPS is - of course - a key part of network security and privacy, but I'm not going into it in this article at all. This, right here, is the only mention of SNI, and ECH, and I'm not even expanding them.

Sorry. I'll write something else on these later!

It really is always the DNS, sort of.

The DNS is a crucial, critical, and central part of the Internet. While it's not quite a single point of failure, DNS problems have an outsized effect on the rest of the system.

I remember back in around 1997 or so - 17th July 1997, I looked it up - every root server dropped offline (except k), and caused mass disruption for several hours. Just 10 machines offline and the Internet - as a whole - "went down". These days there's a couple more root servers, and besides, each one of those IP addresses goes to several - perhaps hundreds - of actual servers. I don't think any root server has been offline since.

And even today, relatively isolated DNS problems - or even just problems with the data in the DNS - can result in much of AWS dropping offline for hours.

But ultimately, most of the "it's always DNS" problems - including that AWS outage - turn out to have root causes outside of DNS. The average DNS server looks at 99.999% uptime and considers it amateurish. Really, it's always ARP, or Terraform, or a digger. That mass root server outage in 1997? A US exchange point, MAE-East, had a bad configuration update to a router and went offline. The servers themselves were actually fine.

It's just that DNS will often be the first thing you'll notice go as a result of any outage at all - and the knock-on effects will be massive.

Nearly Offline Revocation Status Checks for JWT

Dave Cridland — Tue, 04 Jun 2024 08:13:44 +0000

The Problem

The industry standard approach for a token authentication system is to use a JWT with a limited lifetime - the "id token" - with service endpoints, forcing a stronger reauthentication with a central auth system periodically.

These id tokens are verified "offline" - meaning the central auth system is not contacted. This is a useful property as it allows a significantly improved response time for the endpoint. If the central auth system is located only on one side of the Atlantic, for example, then online verification would lead to around 200ms of additional service endpoint latency on the other side.

If these tokens are leaked, however, this means there is no way to signal this - the id token remains irrevocably valid until it expires. Adding an online revocation check would eradicate all the benefits of using the system in the first place.

A Solution

Firstly, every id token should have a unique identifier associated with it. There is no harm in these being eventually reused, as long as they are reused only well after the original token has been expired. I call this the revocation id.

If a token is to be marked as revoked - either automatically via taint failures or explicitly - this revocation id is added to a list (perhaps a database table).

A new central auth endpoint can now check if a token has been revoked - an online revocation check that we want to avoid if at all possible.

Next, I propose adding a shared Bloom filter to the system, maintained by the central auth system. It can be broadcast out on change to service entities via publish-subscribe (eg, Redis) or simply fetched on a short cadence (say, once a minute, or even less).

A Bloom filter is a probabalistic mechaninism for optimising the decision of whether a value is in a set, so by distributing just the Bloom filter values, this obviates the need to check most tokens in an online revocation check.

Bloom filters work by checking if the hash of some value has been binary ORed into a value - multiple hashes are used to reduce the probability of a false positive. For example, if we used SHA-256 and SHA-512, we could check like this:

# Pseudocode, really
def in_bloom(bloom, revocation_id):
  if sha256(revocation_id) ^ bloom.sha256 != sha256(revocation_id):
    return False
  if sha512(revocation_id) ^ bloom.sha512 != sha512(revocation_id):
    return False
  return true

I propose using, as the hash algorithms, a set of HMAC-SHA-256. By using a single algorithm, adding an additional HMAC key is trivial in code, and allows this to be tweaked by operational experience.

This means the Bloom filter will be a short array of 256-bit long binary values. One might be sufficient for smaller systems; I don't think it'd need to be higher than four ever, though measure measure measure.

Finally, to reduce computational load, I suggest calculating the HMAC-SHA-256 values of the revocation id and placing this in the JWT; this essentially trades CPU time for JWT size.

Result

At this point, you have a recovable token with a very low revocation latency, but effective offline revocation checks (and the advantages in latency this gives you).

Subroutines

Dave Cridland — Thu, 18 Mar 2021 20:16:56 +0000

A Unit Of Code

A subroutine is a callable unit of code.

It may surprise you to find that not all languages name their subroutines "functions". Pascal - not that anyone writes Pascal anymore - distinguished between "Procedures" and "Functions". The latter always returned a value, the former could not. Other languages, like BASIC, stuck with "subroutine", giving us GOSUB.

But whatever the name, the key thing is that you can call a function as many times as you like, and from the caller's perspective, it's just like an operator or statement. When it completes, execution picks up where it was called.

Sometimes these functions return a value. Sometimes they accept values - called "parameters" or "arguments".

They usually have a name - a function identifier - but sometimes the name is more complex than just a simple name.

This is a deep dive into functions, how they work, and what to do with them.

The low level

At a low level, in languages like C, something like this happens on a function call:

First, the caller puts the arguments somewhere the function code can find them. Next, it places a hidden argument of where the function was called from - a Program Counter value or equivalent.

Then the actual call occurs, and execution moves from the call site to the function body. Most CPUs actually provide an instruction for this and the later return, which will handle the Program Counter storage for you.

The function then does its stuff, getting the function arguments, processing them, and calculating a return value if any. Then finally, it returns.

The return process is the reverse of the calling process - the return value is placed somewhere, and the Program Counter is restored. Execution then continues from where it left off at the call site.

In general, the place where the function call arguments, return values, and local variables are placed is called a "stack frame". This naturally gives a variable scope for the function, and a clean lifetime for any values created during the function call.

Each call adds a new stack frame to the end, and each return removes it again. In a lot of languages, the program simply terminates once the stack is empty of frames. Too many stack frames will fill the stack and cause a fatal error.

Even where languages don't use actual stack frames, this terminology remains - hence we talk about "the call stack", "stack traces", and so on in all languages.

Call me by my name, oh, call me by my value...

In a language like C, a copy of the variable or expression is placed in the stack frame. This means that any change to the function argument within the function won't propagate back to the caller:


int called(int a) {
  a += 2;
  return a;
}

void caller() {
  int b = 0;
  int c = called(b);
  c == 2; // c picks up the return value here.
  b == 0; // b is left unchanged; we passed a copy.
}

This is known as "call by value".

Because C has reference types - types which hold a reference to some other value, rather than the value itself - we can also pass in the reference by value, giving the function the same reference, and allowing it to use the same value.


int called(int * a) {
  // a is a "pointer to int", a reference type.
  *a += 2; // "*a" dereferences, reaching the value.
  return *a;
}

void caller() {
  int b = 0;
  int c = called(&b); // Pass a reference to b, not b's value.
  c == 2; // As before.
  b == 2; // This time, we've changed the value.
}

This behaviour is called "call by reference", and it allows a function to manipulate the values passed into it.

Some languages - including Javascript, Python, and several others - implicitly use reference types in many (or even all) cases. This means you'll always end up with functions able to manipulate the value of objects unexpectedly:


function fn(oo) {
  oo.foo = 1;
}
function fn2(ii) {
  ii += 2;
  return ii;
}
o = {foo: 0};
i = 0;
fn(o); // Implicitly call by reference.
o.foo; // 1, because fn changed it.
fn2(i); // Returns 2
i; // still 0, because primitives are passed by value.

There are other possibilities - Swift has in-out parameters giving you "call by value-result", but in practice these are generally doing "call by reference" underneath so you needn't pay that much attention. "Call by reference" is, of course, really "call by value" with a fake moustache and a reference type, but the distinction is important.

Returning a Value

When a function returns a value, the distinction between returning a value or a reference can be extremely important.

In C, all reference types are explicit, but also the local variables are likely to vanish - returning a reference to a local variable gives you a dangling reference, which will cause some impressive crashes (or worse).

But you can still return a reference to some value that isn't a local one.

In other languages where objects are always referenced, then the language takes care of this for you. Examples here include JavaScript, but also Python and others.

Returning some Values

Usually, you can only return a single value from a function, but there are two solutions to this limitation.

Firstly, you can return some aggregate type. A typical Python idiom is to use a tuple, and then unpack the tuple at the call site, all of which can be done transparently:


def fn() -> Tuple[int, str]:
  return 1, 'A string'


i, s = fn()

In other languages, you might need a record type or an array.

JavaScript allows you to do something broadly similar to the Python case with restructuring and other shorthands:


function fn() {
  i = 1;
  s = 'A string';
  return { i, s };
}

const { i, s } = fn();

The alternative is a solution we've already touched upon - call by reference allows the function to provide the results by manipulating the arguments. This is often used by C for this purpose - there's an idiom involving passing reference types to reference types in order to get back a reference to a newly created value:


bool create(int **f) {
  *f = (int *)malloc(...); // Allocate memory
  // Initialize (*f).
  (**f) = 1; // Dereference twice to get to the actual int...
  return true;
}

void caller() {
  int *f = NULL; // Pointer to nothing.
  if (create(&f)) {
    (*f) == 1; // True at this point.
  }
}

Don't worry too much about the syntax there (and I accept that double-pointers like that are confusing).

While this deliberate manipulation of arguments seems painfully complicated, it's actually very useful, and is how - in practice - most object methods work.

Not Returning Values

Most modern languages have chosen to unify functions and procedures. C did this by having a special non-type, void, which cannot have any value. A function "returning void" actually returns nothing, and an attempt to assign the return value gives a syntax error.

JavaScript and Python always return a value, however - it's just that it might be a special placeholder value. JavaScript uses undefined here (both a primitive type and a value), whereas Python uses None (the sole possible value of the type NoneType).

The distinction isn't that confusing in practice, but it does mean that in both cases, you can still assign the return value, though it's not likely to be useful - and might be an error.

Naming and signatures

When we call a function, the compiler or interpreter needs to do several things.

First, it needs to find the function declaration. Functions are much like variables - indeed, in many languages they are variables. As such, they are declared somewhere, and in most languages that declaration will also include a definition - in other words, the function's declaration includes the function body containing the actual code. In C and C++, the declaration and definition are usually distinct.

Secondly, in a static typed language, it will need to examine the types involved.

Functions have a return type, and each argument has a type as well - in a dynamic typed language these aren't present.

The arguments you're using, and the way you store the return value, will have to be resolved against the function arguments. In static typed languages, this might result in implicit conversions. Many languages also have optional arguments, which have defaults when omitted.

These details - the types, arguments, defaults and so on - are called the function signature. In a dynamically typed language, the signatures are of course vastly simpler - really, just the name and the "arity", or number of arguments.

Overloading

Some languages provide overloading, where a single function name may have multiple signatures, and the language is free to pick the one that suits best. These are typically picked by name first, then number of arguments, and finally argument types. The obvious exemplar language is C++:


void called(int arg) {
  std::cout << "I was called with " << arg << std::endl;
}

void called(std::string const & arg) {
  std::cout << "I was called with " << arg << std::endl;
}

void caller() {
  called(10);
  called("10");
}

called here has multiple declarations with distinct types, and each declaration also has a definition, or "implementation". If you're seeing a common interface with multiple implementations and thinking "polymorphism", you're not wrong.

Overloading gets a bad rap in some quarters but used well it's amazingly useful - in the code above, we're saving inefficient conversions and adding flexibility for the caller. But if we'd done something entirely different between the two overloads, that'd be very confusing.

Functional languages often allow overloading based on more than just types - certain values, and the "shape" of the data, can be used to overload too.

For example, here's a bit of Erlang which - if I've got this right - will run different implementations of the function depending on whether the array passed in is empty or not, eventually counting the members of the array in a wonderfully pointless and inefficient way:


array_count([]) ->
  0;
array_count([ S | R ]) ->
  1 + array_count(R).

JavaScript does not do overloading - but with a little effort you can do it yourself using a "dispatch function" pattern:


function caller_number(i) {
  console.log("Number variant", i);
}

function caller_string(s) {
  console.log("String variant", s);
}

function caller(arg) {
  if (typeof arg == 'number') {
    return caller_number(arg);
  } else {
    return caller_string(arg + ''); // Convert to string
  }
}

TypeScript does do overloading, but only with the signatures, and not the implementation. To the above, we'd prepend something like:


function caller(arg: string): undefined;
function caller(arg: number): undefined;

But this is not true overloading, just a way to tell TypeScript how to manage the static typing involved.

Operators

Operators are functions, too, of a sort.

In some languages - like C - the operators represent purely mathematical operations which roughly correspond to machine code instructions - they'll never get compiled into calls like a traditional function call. Nevertheless, they possess many of the same attributes as a function.

They have a name, such as +. They have some arguments, which have types. They return a value, which, too, has a type.

In higher-level languages, they're often heavily overloaded. Look at this JavaScript, for example:


'Hello ' + 'World!'; // Concatenates the strings.
1 + 2; // Adds the numbers.

Some languages, like Python and C++, allow you to write your own special functions which are then used in overload lookup. For example, in C++ we could write:


std::string operator+(std::string const & a, std::string const & b) {
  std::string r = a;
  r.append(b);
  return r;
}

This would then allow two strings to be concatenated just like JavaScript. In fact, C++ has done this for us anyway in the standard library - but unlike JavaScript this is some "ordinary" C++ code in the library (and you can go read it if you like).

Variables

And just as operators can be functions, it turns out that functions can be variables, in turn - or at least, you can keep a function in a variable and pass it around.

In the venerable C, this is done by treating the function name as a variable holding the memory address of the function implementation. The type of the variable is the function signature, sans name.

JavaScript makes this simpler, as do a lot of languages, by having what amounts to a function literal. When we define a function, we're just defining a variable holding the function, a bit like:


const fn = function(a) {
  return a * 2;
}

Recent JavaScript has a simplified form (which has a few limitations):


const fn = a => a * 2;

This is particularly helpful for using small anonymous functions as arguments to other functions, like filter or map. In these cases, such functions are normally known as "lambda functions", or simply "lambdas". Most modern languages have them, though they often have some limitations.

Functional Programming

Of course, I've managed an entire article on functions and barely mentioned functional programming.

But that's because functional programming isn't about functions as in subroutines, but functions as in lambda calculus. Functional techniques can be (and often should be) used in any language, and modern languages capable of "procedural programming" can comfortably handle most of these.

Summary

Functions are the way we break code down into manageable, and reusable, units. Different languages provide different capabilities, like overloading, and they inherit features like static typing from their variables, too.

A firm idea of how functions work and operate is important - likely if you're reading this you knew a lot of it already, but I hope this has helped settle things a bit.

Types

Dave Cridland — Thu, 18 Mar 2021 12:42:48 +0000

Type

Data isn't just bits. You'll have numbers, strings, and more in your code. A "type" is metadata used as a way of indicating what sort of data you have, and how it's going to be used. Passing data of the wrong type into a function is generally going to make things go badly wrong, so keeping tabs on this is important.

You knew this already - but this is a deep dive into types, and I'd make this a series if I actually knew how, along with The Variable, and probably more to come.

O, say can you C?

Yeah, so I know I tagged this with JavaScript. But first, I'm going to have to talk about C.

For several decades, even across different types of CPU, all machines have used a flat memory model with a single address system for both code and data, with every byte being 8 bits (though we often read them as a group of bytes up to 64 bits).

This means that just looking at a particular memory location in isolation, there's no real way to tell if something is an integer of 80, or a 'P' character, or (for IA32) the opcode for PUSH EAX - the bits in memory are the same. An assembly programmer must simply remember where they had put what, and what it was for. But as symbolic languages came into vogue, remembering became the job of the language.

C is a thin veneer of symbolic language over ASM. There are variations which are even closer - C-- for example - but C casually hands the programmer raw memory addresses and their contents.

Types in C are essentially reminders to the programmer about what they decided to use a variable for. Sometimes, they're not even reminders:


if ('P' == 80) printf("This compiles without error or warning!\n");

C has just five basic types (counting bool, a recent addition) and three are just integers (including char, which is normally used for character data). It supplements these with an address type (a "pointer") that is itself typed, a special "void" type, a "struct" type for building up records, and some modifiers to alter the width (ie, number of bytes).

Thanks to (mostly) Claude Shannon, we know we can take these few types and process any information at all. Strings, in C, are just arrays of char type integers treated as characters, for example - yet C does not have an actual string type at all.

You can switch between several types at will in case you change your mind on what sort of data you meant, or how you want to treat it.


char p = 'P';
if (++p == 'Q') printf("Well of course it does.\n");

Most languages we use these days have a stricter view on what types mean, but fundamentally it's still about remembering what sort of data you have, and what you're meant to do with it. The distinction is who must remember - you or the computer.

Variable type or data type?

In C, the type of a value is only defined by the type used in the variable declaration you're using the manipulate the data, rather than the value itself. This "weak typing" provides the programmer with much opportunity for exciting errors. Getting the type wrong at runtime means hard-to-find bugs, crashes, or worse - many security exploits are based on treating the same data as different types at different times.

This is, surprisingly, the same for C++ as well, despite its stronger typing - though C++ makes such mistakes much harder.

In most modern languages, the data type is part of the value in some way - and sometimes not part of the variable declaration at all.

So in weak typing, the type is bound to the identifier, and in strong typing, it's bound to the value - or even better, both.

Note that there is no actual definition of "weak typing" versus "strong typing" - or rather, there are many. This one is mine.

In JavaScript, a variable name might reference a string one moment, and later an integer - but either way the program will "know" at runtime, because the type is bound to the value. This is known as "dynamic typing".

But this is confusing, both for the programmer (ie, you) and for the tooling. It's much easier to catch all sort of errors if the type is also bound to the variable declaration - a technique known as "static analysis", which a C compiler will give you for free.

So there's a trend (particularly in imperative languages like JavaScript) to ensure a variable only ever references one type of data. This is known as "static typing", and so C is a "static typed" language with weak types, whereas Python and Javascript are "dynamic typed" languages with strong types. Typescript gives you static, strong types, and Python's type annotations give you much of static typing as well - both are actually dynamic typed at runtime though.

The crucial thing is that whether the data is typed via the variable or intrinsically within the value, there is always a type - you cannot have untyped languages beyond assembly.

Type coercion and conversion

While C is relaxed about types, there are times you want to explicitly change the type of data. One case is where you have an untyped memory address pointer - denoted as void * - and you want to tell the compiler (and your future self) that you're going to store and access some specific type (characters, perhaps).

This is done by "casting", a form of type coercion, where we decide as programmers that we know better than the compiler. Broadly speaking, we do not, so type coercion is considered a Bad Thing.

In most cases, type coercion will not change the actual data at all - though in others it will truncate it, often violently.

In TypeScript, we can do it by using "as", like this:


const my_foo = get_a_thing() as Foo;

This is a pure coercion - no runtime checks are involved, we're simply overriding the static typing.

Type conversion, on the other hand, creates an entirely new value of the requested type. Converting an integer to a string might render it in characters, for example. Conversion is always safe from the point of view of correctness, though implicit conversions the language does for you automatically can take you by surprise. Avoiding implicit conversion therefore becomes useful in languages which are particularly over-enthusiastic about conversions, and these languages typically have a === operator and similar.


1 == '1'; // true
'1' == true; // true!
'0' == true; // false

All the above fail when used with === instead of ==. The string conversions to (or from) numeric strings into boolean values are particularly surprising.

But the === will not save you in all cases, since implicit conversions happen all over the place:


true + true === 2; // true.

But note that this is not coercion - this is an implicit type conversion.

Another definition for a strongly typed language is that it won't allow coercion, only conversion (but note that TypeScript allows both, and by my definition is strongly typed).

Structure of Record

C's struct builds up composite types, which are types themselves. C++ builds on this further, and gives us class, JavaScript gives us objects, and Typescript brings them formal type definitions with interface. Other languages will give you other kinds of "record types".

In all cases, a record has a list of "fields", which themselves have names, types, and values. In languages where we can treat the resulting record definition as a type in all respects, these are often called "user defined types", or "UDT" for short.

You may note I've not mentioned methods here - but this is an article about types, and types alone. Object orientation is another matter, for another article. That said, classes are often the same as a "dumb" record type.

JavaScript is a bit weird on this, mind - the type of any object, of any class, is "object", yet classes can and do exist.


oo = class {};
ooo = new oo();
typeof oo; // "function"
typeof ooo; // "object"

Types and Shapes

Some languages - particularly functional ones - tend not to care so much about types beyond the level that C does, but do worry about shape.

So if a data structure has "the right bits", then it can be treated interchangeably with a particular type.

JavaScript's history means that a lot of this practice resonates with TypeScript, and you'll see echoes of it throughout the language design. Other attempted to introduce formal typing into JavaScript went even further along this line of thought.

If you look at, say, Erlang, you can treat different values as distinct types, too - this can be astoundingly useful. So, a record with a "foo" field of "bar" can be treated as a different type to one with a field of "baz" - and we can do this even when other times, we'll treat them the same.

Plain Old Data

In some languages, not all types are equal. In C++, there's a concept called "POD types", for "Plain Old Data", for example. These are unlike more complex classes and are just the C value types (bool, char, int, float, double and their relations).

JavaScript has "primitive" types; number, string and so on. These are broadly similar to C++'s POD types. In the case of JavaScript, this is made hellishly confusing because there's both string (a primitive type) and String (a global object you can make instances of).


s1 = 'A string';
s2 = new String('A string');
typeof s1; // "string"
typeof s2; // "object"
s1 == s2; // true - same value
s1 === s2; // false - different types
s1 === s2 + ''; // true - `+` operator converted to primitive

Summary

Types underpin everything else in programming. Because they're so fundamental to how we make computers anything more than giant calculators, gaining a solid understanding of types is a crucial step on the path from hobbyist to seasoned professional.

Getting types wrong, at any stage, yields pain, bugs, extra work, and catastrophic failures.

Static typing will help you, and the tools, to find these errors before you run the code. Strong typing helps catch these cleanly at runtime. But implicit conversions and the easily misused coercion can still bite you, even if you're using the === operator.

The Variable

Dave Cridland — Sat, 13 Mar 2021 18:41:03 +0000

A Rose By Any Other Name


let a = 1 + 1;

There's some code. It's JavaScript, but it might as well be any of a dozen (or more) other languages. Your challenge? Point to the variable.

It seems easy, except that just because I've asked you, you're thinking this might be a trick question. And it sort of is.

Let's start with the things that are not the variable for certain.

let is a form of declaration. It's definitely not a variable, but it does cause a new variable to be created.

= is an operator, in this case it might be the assignment operator - but might also be an initialization operator, or even a match operator, in other languages. It's causing the variable, newly declared by let, to be created with a particular value.

1 + 1 is an expression, providing that value.

a is what we generally call a variable. But really, it's a name. In some languages (notably C) a variable name always points to a unique value - you cannot have one variable with two names for it - and this is still technically true in C++, which really tries very hard to muddy the waters. In others, including Javascript and Python, many names can point to the same value. In most languages (possibly all) you can have values with no names at all - and if you think this is esoteric, just link of an array: one name covering lots of values.

So in some senses the variable doesn't exist in the source code at all. It is a value, held somewhere in the computer's memory, and the name merely references it - together, they make up the variable.

"Memory" here is a nebulous term. It might be that this is an actual memory location, but it could also be a CPU register. Either way, the value might change over time, and the location might move, but the identity of the value never does.

By thy name I bind thee ...


let a = {phrase: 'Hello!'};
let b = a;
b.phrase = 'Goodbye!';
console.log(a.phrase);
// Prints "Goodbye!"

What we've actually done in the first code is create a variable, initialize it with a value, and finally bind it to a name.

Javascript allows us to later bind the variable to a new name. In this little snippet, we've bound the variable to b as well. Changing the variable's value does just that - the change is visible through both bound names.

We could also do other things, like rebinding the name to a different variable. Somewhat confusingly, Javascript does this using the same assignment operator:


let a = {phrase: 'Hello!'};
let b = {phrase: 'Goodbye!'};
let c = a;
a.phrase = 'What?';
a = {phrase: 'This one.'}; // <--
console.log(c.phrase);
// Prints "What?"

In the line marked with an arrow, we're not changing the variable (like we do in the line above), we're rebinding a. This doesn't occur with, say, a number:


let a = 0;
let b = a;
a += 1;
console.log(a, b);
// Prints 1 0

This is so confusing that Javascript provides an alternate declaration keyword, const, which prevents rebinding. In Java, this would be final. It also makes numbers and other "primitive types" constant, like the const keyword in C or C++.

It's as if the designers of Javascript, faced with a confusing capability, decided to make it more confusing.

... to my service unto death

Values have a lifetime, whereas names have a scope. These two are often (but not always) interlinked.

While the value exists, it takes up a chunk of the memory for the program (whereas names need not). The program can, if it has a reference to the value, read and change it.

While the name is "in scope", the program source can use that name - once it's "out of scope" it will cause a syntax error.

Javascript is, once more, odd here - so let's ignore it and pick the (surprisingly) simpler C.


{
   int i = 0;
   /* Some stuff here */
}

In C, a variable name exists from the point of its declaration until the end of the block (the brace-enclosed statements). In earlier versions of C, variables had to be defined at the top of the block, but that was easy to work around since a block can be used anywhere a single statement can be (it's how if statements work, for example), so if you needed to, you could nest a block. Modern C allows you to declare the variable anywhere.

When the block is exited, the name falls out of scope and cannot be used anymore, and the value is instantly destroyed, its memory freed for use by something else.

C++ makes this a bit more explicit, since if the value is an object, special methods are called when the value is created (the "constructor") and when it is destroyed (the "destructor"). This means you can trivially see when an object is destroyed, and actually do something.

These values and variables - called "automatic variables" in C - are created on the program stack. You can create values with a different lifetime by creating them on the heap, but if you do this, you take responsibility for their lifetime entirely - the program will never destroy them unless you specifically ask it to. Equally, you don't create these values with a name - you'll instead get the memory location back (a kind of number, at least usually), and have to store that in turn as a more traditional variable somewhere.

Many languages prefer not to make the destruction explicit in the same way - these are known as "garbage collection" languages. Java, Python, and Javascript are all like this - objects are created by the programmer explicitly, as normal, but the language itself decides when you're no longer using them. This usually happens automatically for the programmer (which is nice) but can occasionally be confused by circular references and other problems.


const a = {friend: null};
const b = {friend: a};
a.friend = b;
b = a;
a = b.friend;
// Which cup is the ball under?

In the code above, a references a value which references another value which references itself. Deciding when these values can be discarded is tricky.

But for the most part, this usually "just works".

In the vast majority of languages, scope works in the same way - "local" variable names created within a function are visible from the point of declaration through to the end of the function. C's nested blocks mean that some names have a reduced sub-scope of that function. Calling another function creates a new, empty scope - the variable names from the caller's scope are not visible to the callee.

Global variables - names created outside of a function - are "in scope" to everything, and since anything might change them unexpectedly, it's best to avoid these. Many languages have a module scope as well which behaves similarly.

Member variables - more properly called "object fields" - are only in scope inside the methods for that object.

Javascript is complex here, since the scope depends on how they're declared.


a = 'Implicit declaration';
var b = 'Explicit declaration';
let c = 'Let';
const d = 'Const';

let and const both operate the same way for scope, which is largely the same way as C as described above.

A minor difference here is that Javascript "hoists" the name creation (but not the value creation) to the beginning of the block. This is primarily of importance for the interview question, "What is Javascript variable hoisting?", and is otherwise pointless and confusing.

var, though, creates a new variable name - which is dutifully hoisted to the beginning of the scope - but which is visible through the entire function. This is pretty weird.


function call_me() {
  // aa actually created here.
  console.log('Caller start:', aa);
  var aa = 0;
  if (aa === 0) {
    var aa = 1; // <--
  }
  console.log('Caller end:', aa);
}

call_me();

You might think that the line marked with an arrow declares a new variable - but it doesn't, it just assigns the existing one a new value.

This behaviour is vital for, again, interview questions. Just use let or const.

You can also define a variable implicitly, by just assigning a value to the name. What this actually does, though, is define a new global variable (or module/file scope variable, strictly) - even if you're in a function. This is probably not what you expected to happen. Try this:


function call_me_too() {
  console.log(typeof bb);
  bb = 'Weird, huh?'
  console.log(bb);
}

console.log(typeof bb);
call_me_too();
console.log(bb);

A summary

The moral of the story is:

Use const - if you can - or let - if you can't.
Thank ESLint for finding this kind of stuff for you.
Anything else is for answering interview questions.

Honest Security

Dave Cridland — Tue, 08 Dec 2020 17:32:49 +0000

Honestly?

Not that long ago, I was in a company working heavily in cybersecurity.

One day, I started as usual, by opening my company-provided MacBook, and went to read the day's announcements. I'd just started to read—

The screen blinked off.

Surprised, I nudged the mouse, and sure enough, the screen came to life again, with a password prompt. Odd. I logged back in, found my place and started to—

The screen blinked off again.

What the heck?

The User as the Problem

Device Management solutions are pretty awful things. They enforce some arcane policy by changing your settings, usually without telling you. You, the user, have no control. In our case, we were a consultancy literally filled with experts in the cybersecurity industry, yet our laptops were working against us.

It was simply infuriating. In this case, a bug in the device management solution had meant that in enforcing a screen timeout, it enforced a one minute screen timeout.

This meant that we were unable to work without gently moving the mouse near constantly. Several of us gave up, and downloaded the source for an open source app that caused the mouse to "jiggle" when left alone, and defeated the errant software.

If you think we were wrong, just bear in mind that we frequently had to give presentations to key customers. Having to change slides at least once a minute would be a challenging presentation style.

But fundamentally, this situation arose because in the security world, the user is not trusted or involved. They are seen as part of the problem - not part of the solution. Surely, in our case at least, our team mates were an asset?

In fact, aren't the staff always the front line for any organisation's security posture and device health?

The Insider Threat

All too many cybersecurity firms - those with impressive front pages with pictures of green-lit, hoodie-wearing hackers - like to talk about The Insider Threat. In capitals, just like that.

What they tend not to note is that the insider threat - while very real - comprises almost totally of people making honest mistakes. Trying to prevent mistakes by enforcing that the mistakes cannot be made has two problems. First, it is very complex - and, as we saw, prone to error. Secondly, it often damages the productivity of employees.

Surely the best way to reduce errors like this is by inclusion and education - turning your staff into a security asset, rather than a liability?

Surely security should be more than saying "No"?

Plenty of security experts have already found, for example, that the best way to reduce the effectiveness of phishing attacks is to send phishing attacks to users periodically, gamifying the task of spotting and avoiding them.

After all, this protects not only their corporate email, but their personal email, too - and you can bet that a clever attacker will target that, too. By involving users in their own security, therefore, you are protecting areas that enforcement could never hope to cover.

Working from Home - and back again

As "Bring Your Own Device" and working from home builds momentum, the lines between corporate security and personal security blur to an unprecedented degree.

Just as we don't want our employers to gather information on our home lives systematically, we obviously don't want them to gather information on our personal devices without our understanding and consent.

For companies with staff in Europe, California, and other places around the world, this is a matter of more than idle concern. The GDPR makes gathering personal data without consent illegal. Perhaps worse, it requires companies to provide the data they do collect back to the user on demand.

Clearly, then, the old model of blind draconian enforcement isn't sustainable, even if it were desirable.

Security Leadership

What's needed is a model of corporate security that works in the best - and most effective - traditions of leadership. As security leaders, we should draw our users with us, rather than trying to corral and drive them from behind.

We need to reset the relationship users have with security. We can transform it into a positive force for not only the risk management of the company, but the personal safety of those we work with.

This will make our users happier - and perhaps even more productive. But it will also reduce the risks from security failures to the company as a whole.

Honest Security

Thoughts like these are behind the emergence of a new model of corporate security - "Honest Security". Built around concepts like consent, transparency, and inclusional security practice, the intent is to reverse the adversarial posture of security versus user.

I am not, I admit, the least cynical person on the planet. In the cybersecurity world, there's plenty to be cynical about, after all. I'm fully expecting a series of companies to jump on this bandwagon in name only.

But if the outcome is that security becomes less of a barrier and more of an enabler, I'm all for it. If this is a buzzword, it's a buzzword to watch.

Efficient INSERT MULTIPLE with Postgres

Dave Cridland — Fri, 17 Jul 2020 22:37:26 +0000

Foreword

I'd like to apologise for the lack of cover art. In my defence, I did search for a suitable image to illustrate "multiple insertion", and I feel it important to warn anyone else never to do the same.

Look Familiar?

Do you have code that looks like this?

new_id = db.query("""
  INSERT INTO foo(blah, wibble)
  VALUES($1, $2)
  RETURNING id""",
  "blah", "wibble")
db.query("""
  INSERT INTO other(foo_id, floogle)
  VALUES($1, $2)""",
  new_id, 42)

Maybe it's more complicated, maybe it has SELECT statements and all sorts.

But it works. So why am I going to suggest changing it?

Round trips

The moment we introduce a network connection, we end up with two key parameters for performance. There's "How long something takes to execute", and "How far is it away". The former we have some control over; we can write things more efficiently, add database indexing, boost instance sizes and whatever else needs doing.

The latter, though, we have little control over. If the round-trip time to the database is 5ms, then that code above will take a minimum of 10ms, no matter how fast the database and app service is.

There's other posts that will take you through the delights of query optimisation - I hope, and if not, then nag me and I'll write one.

What we're going to do is make the round-trips go away - and maybe make things a bit faster.

INSERT MULTIPLE

Sadly, there's no such thing as INSERT MULTIPLE. You can put multiple rows into a single table (INSERT ... SELECT ...), but not a row into multiple tables.

You could use a trigger here - that will absolutely work, but I find triggers that are beyond really trivial cases to be astonishingly difficult to test and debug.

Instead, we need a technique called a "Modifying Common Table Expression", or "Modifying CTE".

Common Table Expressions

Normally, any sign of WITH in a query has my hackles up. It's generally the sign of an overcomplex query on a schema not designed to service it.

At their simplest, they look like a rephrasing of a sub-select JOIN:

WITH thing AS (
  SELECT id, blah FROM foo
  WHERE wibble LIKE '%ibble'
)
SELECT floogle FROM other
JOIN thing ON other.foo_id=foo.id

But the magic is that the WITH causes the query to be a fully-named table - a Common Table Expression - so you could use it multiple times, or even within a second Common Table Expression.

WITH thing AS (
  SELECT id, blah FROM foo
  WHERE wibble LIKE '%ibble'
),
other_thing AS (
  SELECT id, foo_id, floogle, blah FROM other
  JOIN thing ON other.foo_id=foo.id
)
SELECT id, foo_id FROM other_thing
JOIN table_i_havent_mentioned_before t ON t.id=other_thing.id

The query optimizer will be clever here, and knows it needsthing before other_thing can be ready. But in practise, it'll also treat the entire query as a single SELECT, so this isn't that exciting.

But what if we don't use a SELECT in the CTE, but an INSERT, UPDATE, or DELETE?

Modifying CTE

WITH step_one AS (
  INSERT INTO foo(blah, wibble)
  VALUES($1, $2)
  RETURNING id
)
INSERT INTO other(foo_id, floogle)
SELECT id, $3 FROM step_one

This does the same as the (pseudo) Python at the beginning.

Postgres will run step_one first, as the outer statement depends on it, and then run the outer statement with the result - just as the Python did before it. Only this time, it's all in a single round-trip.

Let's try something more complicated - how about four statements?

MOAR Modifying CTE

new_id = db.query("""
  INSERT INTO foo(blah, wibble)
  VALUES($1, $2)
  RETURNING id""",
  "blah", "wibble")
other_new_id = db.query("""
  INSERT INTO bar(blook)
  VALUES($1)
  RETURNING id""",
  "blah", "wibble")
db.query("""
  INSERT INTO other(foo_id, floogle, bar_id)
  VALUES($1, $2, $3)""",
  new_id, 42, other_new_id)

Here, we have some Python that executes two statements, one after the other, and inserts the new ids from both in a second table.

In Python, we have to run one after the other - you can't run statements concurrently in a single transaction - so 3 round-trips, 3 statement executions. (Worse actually, since the transaction cost an additional 2 round-trips, for a total of 5.)

But as a modifying CTE statement:

WITH step_one AS (
  INSERT INTO foo(blah, wibble)
  VALUES($1, $2)
  RETURNING id
),
WITH step_two AS (
  INSERT INTO bar(blook)
  VALUES($3)
  RETURNING id
),
INSERT INTO other(foo_id, floogle, bar_id)
SELECT s1.id, $4, s2.id FROM step_one s1, step_two s2

This uses just one round-trip - but also, step_one and step_two are executed concurrently, because they don't depend on each other... so only two statement execution times.

Also, it's a single statement, so you no longer need a transaction for isolation.

I admit, though, that the parameters are getting hard to track. Hey, I know what would solve this:

EVEN MOAR CTE!

WITH my_data(blah, wibble, blook, floogle) AS (
  VALUES ($1, $2,$3, $4::BIGINT)
),
WITH step_one AS (
  INSERT INTO foo(blah, wibble)
  SELECT m.blah, m.wibble FROM my_data m
  RETURNING id
),
WITH step_two AS (
  INSERT INTO bar(blook)
  SELECT m.blook FROM my_data m
  RETURNING id
),
INSERT INTO other(foo_id, floogle, bar_id)
SELECT s1.id, m.floogle, s2.id
FROM step_one s1, step_two s2, my_data m

Look! Variables! (Sorta!)

Note that I've used a SQL cast to ensure my floogle value is the correct BIGINT type, though normally the libraries get these right for you - but for timestamps and things, it might get hard to figure out.

Conclusion

Modifying Common Table Expressions are powerful tools for making a range of common patterns involve a lot less back-and-forth between the application service and your database.

Not only that, but despite the arcane syntax, they can often be faster, and with a little effort, easier to read. They're also easier to debug than triggers.

Have fun!

Smart Pointers in C++

Dave Cridland — Sun, 12 Jul 2020 14:59:27 +0000

Smart Pointers

Smart Pointers are clever little things. Understanding them is key to writing solid C++, and this article aims to take you on an ever deeper dive into them.

Resource Acquisition Is Initialisation

The golden rule of C++ is that the compiler will do a lot of work for you as long as you put your resource acquisition - particularly memory - into a constructor somehow, and ensure the resource is cleaned up by a destructor.

The C++ compiler will then ensure that your resource, whatever it is, is always cleaned up when you exit the variable's scope - whether that was reaching the end of the scope normally, returning from a function call, having the parent object destroyed, or having an exception thrown.

The technique of doing so is called Resource Acquisition Is Initialisation, or RAII for short. If you only know one thing about C++ best practises, it should be this.

Memory

So it's something of a surprise that ordinary pointers don't do this - instead, "bare pointers" do no clean-up at all. That makes code like this risky:

{
  auto * p = new std::string("Hello World!");
  std::cout << *p << std::endl;
  delete p;
}

We have to explicitly delete the object we created, and should the output generate an exception, we'll lose track of that memory entirely.

This is a contrived example, of course - it's trivial to just use a stack object here, instead - but non-contrived examples are more difficult, so we'll stick with this.

A (Too) Trivial Smart Pointer

Just tracking the memory is quite easy. We'll grab the pointer into an object at the earliest opportunity, and delete the object on destruction:

class smart_string_pointer {
    std::string * const m_ptr;
  public:
    smart_string_pointer(std::string * const ptr)
      : m_ptr(ptr) {};
    smart_string_pointer()
      : m_ptr(nullptr) {}
    ~smart_string_pointer() {
      delete m_ptr;
    }
};

So far, so good. I've defined the pointer (but not the string it points to) as const, to indicate that we don't actually want to change it.

We can use this like:

{
  smart_string_pointer p(new std::string("Hello World!"));
  // Erm?
}

OK, so we can't get the pointer, which makes this a bit useless. Luckily, C++ gives us operator overloading to help here.

// ...
  std::string & operator*() {
    return *m_ptr;
  }
  std::string const & operator*() const {
    return *m_ptr;
  }

Now we can just use it like a normal pointer - if it's a const smart pointer, than the object is automatically const too.

There's a similar overload available to us for the arrow operator too - we do that in the same way.

{
  smart_string_pointer p(new std::string("Hello World!"));
  std::cout << *p << std::endl;
} // p->~smart_string_pointer() called here and cleans up.

But this still has problems - the C++ compiler is going to be simply too helpful here, and create us a copy constructor, a move constructor, and assignment operators - all of which will copy the pointer. When the other object is destroyed, that means we'll have a pointer which has already been deleted.

When we try to delete that a second time, we touch on what the standard calls undefined behaviour, and that generally means the program crashes:

{
  smart_string_pointer ptr(new std::string("Hello World!"));
  {
    smart_string_pointer another_ptr(ptr); // Works!
  } // another_ptr->~smart_string_pointer() called, deletes object.
} // ptr->~smart_string_pointer() called, crash!

We're going to need to solve this. And that means deciding what to do when we try to copy (or move) a smart pointer.

A Short Interlude About Templates

I don't really want to have to make a new smart pointer type for every different type I'm pointing to. That means making it generic, by using templates.

People think templates are complicated, and that's really not so. All a template is is just some code where there's a variable that contains a type.

We use a different syntax for these because they're handled at compile-time, not runtime, but beyond a slightly unfamiliar syntax, that's it.

So let's make this smart pointer we have nicely generic.


template<typename T>
class smart_ptr {
  T * const m_ptr;
public:
  explicit smart_ptr(T * const ptr) : m_ptr(ptr) {}
  smart_ptr() : m_ptr(nullptr) {}
  T & operator*() { return *m_ptr; }
  T const & operator*() const { return *m_ptr; }
  T * operator->() { return m_ptr; }
  T const * operator->() const { return m_ptr; }
  ~smart_ptr() { delete m_ptr; }
};

I've included the arrow operators this time, and also made the pointer constructor explicit, which prevents it being used in object conversions we don't ask for.

OK? Let's move on.

Move It!

If we intend that a smart_ptr's object can be moved into another one - useful for being able to return them from functions, for example - we can do that by overloading the move constructor and assignment operators:

  // ...
  delete smart_ptr(smart_ptr const &);
  smart_ptr(smart_ptr && other) : m_ptr(nullptr) {
    std::swap(m_ptr, other.m_ptr);
  }
  delete operator=)smart_ptr const &);
  smart_ptr & operator=(smart_ptr && other) {
    delete m_ptr;
    m_ptr = nullptr;
    std::swap(m_ptr, other.m_ptr);
  }

So, we need to delete any pointer we have, copy the new pointer from the smart_ptr being moved, and then set the smart_ptr's one to nullptr.

You'll see I'm not doing that, quite - instead I set my own pointer to nullptr and swap them, since this is a little safer.

Also, I've told the compiler not to generate implicit copy functions.

If we do this, we should also rename it, and then, with regret, throw it away - what we have there is a std::unique_ptr, and it's a certainty that the one that comes with your compiler will be better written.

Copy It!

If instead we want to be able to have lots of these smart pointers, all pointing at the same object, and copy them about happily, we're going to need to do something more clever.

Because we're going to need to know when to delete the object, we'll need to track how many of these smart pointers exist - only when the last one is destroyed do we delete the pointer.

Moreover, they'll need to all share the same counter.

That's a job for yet another pointer... Let's look at just the simple constructor and destructor cases:

template<typename T>
class shared_ptr {
  unsigned long * const m_counter;
  T * const m_ptr;
public:
  shared_ptr() : m_counter(nullptr), m_ptr(nullptr) {}
  explicit shared_ptr(T * const ptr) : m_counter(new unsigned long(1)), m_ptr(ptr) {}
  shared_ptr(shared_ptr const & other)
  : m_counter(other.m_counter),
    m_ptr(other.m_ptr) {
    if (m_counter) ++(*m_counter);
  }
  ~shared_ptr() {
    if (--(*m_counter) == 0) {
      delete m_ptr;
      delete m_counter;
    }
  }
};

So, when we bring a new object under the control of this shared pointer, we create a counter to go alongside it. Whenever we copy it, we increment the counter. Whenever we get destroyed, we decrement it - if it falls to 0, there are no remaining shared_ptr instances pointing at the same pointer, so we also delete both object and counter.

A confession

And that code, above, doesn't entirely work, and isn't very good anyway.

The reasons are many and varied, and mostly subtle. When allocating the counter, for example, we might encounter an exception and then leak the original pointer.

Luckily, the fix is trivial - if you need this kind of behaviour, just use std::shared_ptr, which has a host of additional features.

And one more thing.

A particular challenge left is the initial object creation. Exceptions thrown at the wrong moment can still leak memory, and we don't want that.

The standard library includes a couple of useful helper functions for this. std::make_unique creates (and returns) a std::unique_ptr with the object you need initialized, and std::make_shared does the same for std::shared_ptr.

The arguments are the same as the constructors of the object you want, so you can do:

{
  auto ptr = std::make_unique<std::string>("Hello World!");
}

Or:

{
  auto ptr = std::make_shared<point>(0, 0);
}

Happy smart pointering!

Why my code looks nicer than yours

Dave Cridland — Wed, 08 Apr 2020 19:30:33 +0000

If I wrote this post entirely in a
monospaced font, you'd probably
stop reading very quickly and
wonder what possessed me to
spend actual effort trying
to make my post less
pleasant to
read.

And we won't even begin to ask why the line length was so much narrower than the space available. I mean... Why?

But the truth of it is that, as programmers, we spend much of our working life painfully reading vast amounts of text that have been formatted and presented in the same way.

Well, you do. I, on the other hand, do not.

For I have a secret.

Every time I setup a code editor, I change the font to a proportional one - usually Deja Vu Sans.

And every time a colleague sees me do that, they stare.

"You can't write code in a proportional font!" they cry.

I ask them why not.

"Because it won't line up!" is the answer.

But you know what? It really does line up very well indeed - because unless you're using some really esoteric languages, you're only ever aligning the beginning of the line, and that means counting space characters. Even in a proportional font, leading space characters have a consistent fixed width.

"It won't look right!"

Oh, but it does. I admit that it takes a little getting used to - looking at code in something like Courier is so ingrained into our psyche that code rendered anything like normal text does look a little weird at first. But after spending a bit of time with it, you realise a few things.

Firstly, it's easier to read. And as a programmer, we read code far more than we write it. The reason why books, magazines, and almost everything else is laid out in proportional fonts is because they're easier to read like that - and we surely want our code to be pleasant to read?

Typographical errors are easier to spot too, because the odd letter combinations actually jar a bit on the eyes.

Secondly, proportional fonts fit a lot more on the page. Horizontally, it's very obvious - you'll overflow you mandated maximal line lengths (don't get me started) with ease, and your primary difficulty will be guessing whereabouts the line ought to end.

Even vertically, a proportional font can fit a bit more in, because the font designs can be considerably clearer at smaller sizes.

But enough of this - you're all convinced it'll look terrible.

Javascript (actually the window-size library), looking pretty.

C++ (this time Metre) - did you even know it could look this beautiful?

Erlang, looking... OK, it still looks ugly. But less ugly. And I'll bet you spot the spelling error.

Even Python, where the strict layout actually matters to the code, looks great in proportional font.

So do give it a go. You never know, you might like it.

The only irony is that this post, of course, was carefully crafted in monospace...

Slow Data

Dave Cridland — Mon, 06 Jan 2020 22:54:29 +0000

A fair amount of my career has involved some pretty appalling networks. I don't mean just because I live in rural Wales - my broadband is actually pretty good - but because I work in "Critical Messaging", and that tends to get deployed where the network is basically awful.

As a result, I giggle a bit when people start to talk about making their app work effectively "even on mobile", because mobile, to me, is an awful lot of bandwidth.

Instead, I've spent time on satellite connectivity, and even HF radio. Satellites only go as slow as modems did when I first used the Internet, mind, but HF radio goes really, really slow. Just as bad, but in other ways, our app is deployed into hospitals, which seem almost designed to block network signals.

How Slow is Slow?

Networks can be bad in any one of three ways. They can be low bandwidth - in fact, most people would expect a slow network to be slow because of bandwidth more than anything else.

Or they can be slow because of high latency. Satellite connectivity used to be relatively high bandwidth, compared to home dial-up, but very high latency. You'll typically have come across this as a "high ping".

Finally, they can just be unreliable. WiFi blackspots and so on can be really frustrating if you're trying to keep a connection up.

Low Bandwidth

Bandwidth is how fast data can be sent - actually how many individually identifiable atoms of information can be sent each second.

In general, low bandwidth is the easiest problem to deal with. Just send less data.

In general, the actual number of bytes on the wire (I can be all proper and call them "octets" if you like) doesn't really matter, because there's signficant overhead from TCP and IP headers in general. But keeping your data into as few packets as possible does make quite a difference.

Ultimately, though, if you've a lot of data to send (for example, a photograph), you'll just have to send it.

In HTTP, it's worth taking a look at the size of requests and responses. Typically, most request and response bodies are far smaller than the headers that go along with them - HTTP/2 helps a lot here by removing repeated headers - this "amortizes" the cost of headers across several requests.

In XMPP, it turns out that the messages are small and have very low overhead - switching from XML here into a binary format (like EXI, for example) makes surprisingly little difference.

High Latency

Latency is how long an individual bit takes from leaving one machine to arriving at another. We rarely actually measure this - it's extremely difficult to measure, for one thing - instead we measure how long it takes to go from one machine to another and back again. This is known as the Round Trip Time, or RTT for short.

Latency has a much higher range than bandwidth in modern networks. Bandwidth above about 40Mb/s doesn't make a huge difference for a single application, whereas latencies still have a visible human effect even when they drop below 30ms.

In addition, networks vary hugely. A good DSL has comfortably low latency - I can ping a typical service in around 16.5ms from mine. 4G, though, leaps to 100ms. 3G is 300ms - the same as fast Satellite, like Iridium. X-Band has higher bandwidth, but you pay with 800ms of latency.

If you think that's slow, try STANAG 5066, a military radio system used within NATO. While it typically runs at a delightfully nippy 2400b/s, that's only in one direction at a time. To get anything back in the other direction, you'll need to wait a whopping 30 seconds.

And that's on an unladen connection - as the data send approaches the bandwidth limit, latencies skyrocket, since the data sits about waiting to be sent.

You might be familiar with packet loss - this plays a part here too, mostly by manifesting itself as even higher latency. In general this is so low-level that we as application programmers never see actual packet loss.

I'll go into this in a bit more detail later for HTTP and XMPP, but ultimately any time you make a request, you're going to have to wait around a full RTT before you see the response.

HTTP and XMPP amortize the latency over several requests when possible, in slightly different ways. HTTP/1.1 uses "pipelining", where a sequence of requests is sent at once, before waiting for the responses, and these are replied to in order. XMPP uses concurrent requests, where each request can be responded to anytime. HTTP/2 also handles full concurrency.

Of note is that HTTP/1.1 will cancel the pipeline and close the connection on any error (4XX or 5XX) - that means that the effective latency of a request cancelled this way can be huge.

Unreliable

Constantly switching networks means that any long-term connection is going to have to be re-established quite a lot.

HTTP has the advantage here - being stateless, there's just TCP and TLS to reestablish. For XMPP, however, there's a lot more state, and we've had to develop tricks like XEP-0198 to counter that.

Bandwidth Delay Product

As a last little consideration, if a network drops (the WiFi goes away, or the 4G signal fades, or whatever), the data that could be "in flight" is given by Bandwidth x Latency. In high-performance networking, this becomes an issue concerned with TCP Window size tuning, but in my world, it translates into potential data loss every time a device switches bearer.

XMPP's XEP-0198 tackles this problem very well, but an HTTP pipeline filled with non-idempotent requests that goes missing could easily ruin your whole day.

HTTP

Looking at the timing diagram for HTTP gives you some idea of how long things can take on a bad connection. Here I'm counting in RTTs (and for simplicity, not that it matters, assuming that latency is symmetric):

As you can see, assuming DNS takes a single RTT (an A record lookup), then it'll take 4 RTTs before we can send the first request. We can pipeline afterward, but even so it's going to be 5 RTTs before we get a response.

If that first request fails, or we lose the network after it, or we're waiting around too long (the connection will be closed anyway after a few seconds), a second request will need all those RTTS repeated.

Luckily, this isn't quite true normally - firstly, the DNS lookup can usually be cached, so we can forget about that entirely. Secondly, TLS has some tricks up its sleeve if you're rapidly reconnecting, allowing another RTT to disappear:

Reducing even further is possible - TLS 1.3 gives us "Zero Round-Trip" (0-RTT) handshakes, at a cost of increasing security risk, and QUIC (and HTTP/3) give us a replacement for TCP that reduces the handshake there, too.

XMPP

XMPP is a stateful, connection-oriented protocol. This is very effective when we have a stable network and lots of interaction to do, because the connection will stay live for a long time - hours or even days, compared to less than a minute for typical HTTP - and clients only need a single connection, always to the same server.

But this comes at a cost in terms of the connection setup. A cold setup is over twice as long as HTTP, and that's before considering getting to the meat of the protocol - presence and messaging:

At this point, we can start receiving some traffic - though a typical client will need to wait at least another RTT before getting presence and messages.

Some of this is because XMPP uses more DNS than HTTP, of course, but some is because it uses inline negotiation for TLS, has a mandatory authentication step (here using a strong mechanism), and so on.

As with HTTP, this shrinks down a bit with DNS caching and TLS session resumption. That would bring us from 12 RTTs to a mere 9. But there's clearly more we can do.

Working from left to right, we can get rid of the inline negotiation for TLS, and go to TLS directly, just as HTTP does. That's covered in XEP-0368, which ironically reverts to the same way the protocol used to work when it was called Jabber, before the IETF took it on. Direct, or immediate, TLS gains us another 2 RTTs - so we're now down to 7.

Authentication in XMPP is pluggable, because it operates using the SASL framework (which is also used by IMAP, SMTP, and LDAP). There's plenty of 1-RTT authentication mechanisms available, and some don't compromise security too badly - I mean, no worse than anything used in HTTP. This brings us to 6.

So far, we've only used widely-supported techniques. But if we move into more advanced - but also more experimental - territory we can save even more.

The way SASL is wired into XMPP could also benefit from some improvement. Because XMPP is designed to be extensible, it allows us to replace even complex parts of the protocol like this - XEP-0388, known as SASL2, gives us a slightly more efficient, and much more extensible, SASL profile than the original standard. Just switching saves us another round-trip, so we're now down to 5.

If we're somewhat brave, we can actually reduce this further by caching the server's SASL configuration, pipelining that green bit in the middle. Technically this is frowned upon, but relatively safe, and saves us another RTT, so hey ho.

This is now faster than a cold-start HTTP, which is quite fun. We can reduce it even further, though, by using Instant Stream Resumption. A fairly common extension, XEP-0198 allows us to switch connectivity if (for example) WiFi drops by using a token - this saves us all the additional round-trips that a complex IM client will need to do at some point. ISR takes this a step further and builds on SASL2 to give us a mere 3 RTTs.

This is now as fast as HTTP/1.1 or HTTP/2 will go without introducing risky compromises like TLS 1.3 0-RTT - which are considerably less risky with a solid SASL mechanism in play.

Well, if only anyone was using either SASL2 or ISR quite yet, anyway - I did warn you these were experimental.

Slow

When dealing with "long thin" networks - especially when these networks are unreliable - some challenges are unavoidable. There's nothing we can do to transfer a JPEG image any faster without compromising on visual quality.

But latency is both a worse problem and one we can do a lot to help with. The cutting edge of both HTTP and XMPP has made a huge number of advancements in this area, and if you're working in this space (or just need very snappy connections), it's worth looking at the low level to ensure you're getting the value from your stack.

And, as ever, if you are playing around with XMPP on awful networks, come and join the conversation at the XSF!

Sending a Message

Dave Cridland — Mon, 18 Nov 2019 16:23:18 +0000

How hard can it be?

Messaging is something of a niche - you can find web developers by the truckload, but when you're after someone with messaging experience, there's really very few of us around.

That's probably because messaging is so simple, right? All we need to do is take a message from one place and put it into another. How hard can that be?

A Discussion about what a Message is

Messages can be anything - a heat sensor might emit the current temperature, or we might want to send log messages, or status updates.

But it's probably easiest to consider the case of text chat, since we're probably all familiar with it.

In its simplest form, a text message can be simply the text itself, whom it's from, and (probably) some indication of where to send it. We'll start with this, then.

We could use any format to discuss this, but it's more useful to work with a concrete example, so I'm going to use the XML syntax of XMPP. XMPP is an Open Standard messaging protocol, and it's used more or less everywhere messaging becomes critically important, like the military, governments, and hospitals. Also, it's used quite heavily in games - Fortnite, for example. There are client libraries for every language, and lots of different servers to choose from too.

XMPP uses addressing based on something that looks very like an email address with an optional "resource identifier" added onto the end (which, fact-finders, I'll leave out of the examples). There are differences between email addresses and those of XMPP, mostly around Unicode support (XMPP has it) and legacy support (XMPP doesn't need to support X.400).

So here's a very simple text message in XMPP:

<message from='me@myserver.net' to='you@yourserver.net'>
  <body>Hey, this is my first message!</body>
</message>

This is an entirely legal XMPP message, with all the required metadata - all the stuff that would, in an email message, be in the headers. It's pretty small, and hopefully the XML won't put you off too much. Normal developers never have to deal with XML at all when using XMPP, any more than web developers have to deal with header parsing - but it's convenient to show, and XMPP's use of XML is relatively clean.

Loss, and Tragedy

XMPP works over TCP - a reliable connection - but there's a lot that can go wrong.

If we lose connectivity - if the WiFi goes down or the 4G signal drops - we can't easily know if the message got through before the network died entirely.

Sometimes we do - TCP gives very strong guarantees in some cases, so we know that if we send a second message and that one gets through, the first one certainly did. But the guarantees of TCP are fundamentally about ordering and corruption rather than simple loss.

Rapid network changes - as you get with a smartphone - make what used to be an edge case on desktop a nightmare on mobile. Dealing with other network types can be even worse - XMPP will operate over military radios which can only transmit or receive, not both, and take half a minute to switch modes.

While someone not getting the message above is mildly irritating, the nature of where XMPP is used means that the outcomes can be fair worse than merely irritating. If we send a message about, for example, new medication for a patient, it's of critical importance we know if it was received.

Acknowledgements

The simplest solution is for the receiver to say they got the message. We can handle this in XMPP by adding an extension. There's two we can use, either the older (and more widespread) Delivery Receipts, or the much newer Chat Markers. I'm going to discuss the latter, because it's a little more interesting from a theoretical standpoint.

First, we're going to add in the additional metadata we need. If we're going to refer to a message by saying we received one, we'll need to have a way to identify which message we're talking about. XMPP handles this by a simple id attribute:

<message from='me@myserver.net' to='you@yourserver.net' id='1'>
  <body>Hey, this is my first message!</body>
</message>

In a real implementation, we'd use a UUIDv4 or similar, but for this example we'll just use an integer counter.

Now we need to indicate to the receiver that we support chat markers. We could do this by discovery - having the receiver ask our client directly - but it's simpler in our case to include this in every message:

<message from='me@myserver.net' to='you@yourserver.net' id='1'>
  <body>Hey, this is my first message!</body>
  <markable xmlns='urn:xmpp:chat-markers:0'/>
</message>

XMPP uses namespaced elements for extensions like this. XML namespaces can get a bit wordy, so we use a URN namespace to keep them as small as possible. The good news is that you can create your own without risk of clashing, using a URL you control.

When we receive such a message, we can respond by telling the sender where we are. But thanks to the ordering that TCP gives us (and XMPP builds on), we don't have to send a response to every message - we can just respond to the last one. Previous messages are guaranteed to be delivered if a subsequent one is.

<message from='you@yourserver.net' to='me@myserver.net' id='2'>
  <received xmlns='urn:xmpp:chat-markers:0' id='1'/>
</message>

There we go. When we receive this, we can show the message has been received (or displayed) by putting a couple of ticks next to the message.

But this acknowledgement is, of course, a message (in the sense of "Messaging") as well.

And so it, too, can be lost...

A Short Interlude about Storming Cities

Imagine, for a moment, there is a fortress city, defended so well that a single army cannot hope to conquer it.

Imagine, further, that there is not one, but two armies arrayed against it - one on each side of the city.

Because the city is astride a river, and has the only bridge for miles within its walls, the general of each army can only communicate to the other by sending a messenger to sneak through the city.

Attacking individually would leave the Generals' armies defeated utterly - in order to conquer it, they must attack at the same time. So all they have to do is send a message to the other General suggesting a time, and know it got through.

But what if the message was lost? The first General would be defeated, so unless the first one knows the message got through, he will not attack. Since the second General knows this, they must send a message back, saying they got the first.

But what if this acknowledgement was lost? The second General would attack, but the first might not, thinking the message hadn't got through. The solution is, of course, to acknowledge the acknowledgement, and ... can you see where this is going?

The Two Generals' Problem is an insoluble problem in messaging. It literally declares that there is no way for both sides to agree on the current state (or, more accurately, there is no way for two parties to simultaneously know the state of the other).

So it looks as if, rather than messaging being quite simple, it's actually impossible. And impossible is quite hard.

If at first you don't succeed...

We can try addressing this by sending messages more than once; but with human messages this becomes tricky quite fast. Humans do not react well to duplicated messages, as we don't typically include the metadata required to spot them at that level.

XMPP's ordering rules really help, but they don't make things perfect (but if you don't have ordering rules at all, then things can go really very wrong in a critical messaging environment).

Besides, we can't blindly resend all the time, since we'd never know when to stop with, for example, acknowledgements. And we can't just acknowledge acknowledgements forever, either - it'd never end.

It would be useful if we could somehow fix TCP, WiFi, and all the rest so that sending a message was more reliable in the first place.

A Place Between Success and Failure

When we send a message in XMPP, we don't actually send it to the other party.

In common with most messaging systems, we send it to our server, and that takes responsibility for it and sends it onto the other party (or their server, in federated cases).

This means that there's another, hidden party we can use, and it knows literally every detail of our connection. This in turn means we can change our connection a bit to make it considerably more reliable.

First, we're going to stop considering a message as simply either "sent" or "not-sent". We're going to introduce a fuzzy state of "maybe-sent". Anytime we send a message over the TCP session, we'll place it into the "maybe-sent" state, and keep a copy.

Now we need a way to find out what state that message ends up in. We can't do this instantly, but we can eventually. So we'll just ask the server periodically how many messages it got. This won't be a message in the XMPP sense - it'd be far too silly. Instead, it'll be a new thing (defined in Stream Management):

<r xmlns='urn:xmpp:sm:3'/>

This is governed by the same ordering in the TCP session as our messages, so it's reliable in retrospect, just like the messages themselves. This means when the server receives this, it knows exactly how many messages have arrived, and can tell us:

<a xmlns='urn:xmpp:sm:3' h='1'/>

Perfect - now we know the server has received our first message, and we can remove it (and any previous messages) from the "maybe-sent" and consider it "sent". It might not have got to the other party yet, of course - but it's no longer our responsibility.

The UX for this is usually a single tick against the message - it was popularised by WhatsApp, which itself uses a private version of this same protocol developed against their weird WEP fork of XMPP.

Of course, if we walk out of WiFi and switch to 4G, this still leaves messages in the "maybe-sent" state - so they might be lost (or might not be).

Where did you come from, where did you go?

We can address this by asking the server when we reconnect. When negotiating the extension, we just say "Here's my previous session id. I got to here, what about you?"

The server then tells us where it got to and resends any messages that we missed, and we do the same. This essentially resumes the session exactly where it broke, and means we've extended the ordering and reliability rules from TCP across to a new session. Shiny.

The specification tells us how this works. We'd send something like:

<resume xmlns='urn:xmpp:sm:3'
        h='4'
        previd='some-long-sm-id'/>

And the server responds with:

<resumed xmlns='urn:xmpp:sm:3' h='1' previd='some-long-sm-id'/>

Oh, phew! So the server did get our message, even though we lost WiFi! Fantastic.

Sometimes this too fails - maybe the server gave up waiting for us to reconnect - in which case our messages can be stuck in the "maybe-sent" state. The best option we have here depends on what the message is - some messages, like Chat Markers, can be resent very safely, whereas for human messages we might choose to flag this condition to the user instead, and let them decide.

What we know we know

At this point, these two protocols are working in combination. We can be confident that when we send a message it'll (eventually) get to the recipient, and when we get a chat marker back, we know they'll have received everything up to that point.

Chat Markers also tell us the messages have been displayed, and - just like text messages - they can be resent automatically if we lose the connection.

The Two Generals Problem isn't solved in XMPP, of course - that would be impossible - but we have managed to make it a genuine edge case, even in very unstable network environments.

XMPP achieves all this by building a multi-layered approach to message reliability, combining existing features like TCP's guarantees with both low-level machine acknowledgements and high-level human ones.

The result is why XMPP is used in hospitals and battlefields - whether real or in a game.

Access Control

Dave Cridland — Fri, 26 Jul 2019 10:41:05 +0000

That chap up there?

He's called Tim. He's an enchanter, and, more germane to this article, he's also an access control mechanism.

Enchanter Based Access Control

Enchanter Based Access Control, or EBAC, isn't available to most developers. It needs a highly trained enchanter, a bridge, and some questions, and is a highly interactive solution.

In general, we restrict interactivity to authentication, and leave authorization as a non-interactive solution.

Plus, it's a little weird, in terms of an example. Let's talk about patient records in healthcare as our example instead. Patient records have lots of parts to them - there's data such as names and addresses, and also medical data, both current and historical. Since almost everyone gets some medical attention at some point, we also have lots of them.

So, how do we protect access to this data?

Authentication gets us to a proven identity, and sometimes that's good enough.

Identity Based Access Control

If you have an identity, that might be all you need. Alice and Bob have access to this data. Nobody else does.

It's a perfectly good way of specifying Access Control Lists, or ACLs. But what happens when Alice leaves the organisation? We need to go through every ACL she's listed in and remove her. Alice's replacement also needs adding in - and that means tracking, somehow, what New Alice needs access to.

So if you've a lot of data - and therefore a lot of ACLs - a little indirection might be useful.

Role Based Access Control

What we could do is group people into types - from the data access perspective, anyway. Managers, Doctors, Developers, Admins, and so on. These different types are called Roles, and it means that your ACLs now just contain a set of Roles, rather than people.

When Alice stops being a Doctor, we just remove that Role form her. A replacement gets the Doctor role. It's vastly simpler to manage.

Often, you can mix and match - an ACL can contain a mix of Roles and Identities, because any Identity is a (specialized) Role.

The trouble is, that still leaves you with a lot of ACLs, and fine-grained access control - where you might have thousands of records to manage - means thousands of ACLs against every record. Or, even, parts of records. Perhaps a little more indirection might help.

What if you could describe the sensitivity of data, and then describe the trust and training of people to handle such data?

Rule Based Access Control

Let's say that all patient records are "Sensitive". The personal information there - names, addresses, in particular - we'll add a tag of "Personal". The medical stuff, well let's just give that a tag of "Medical". So some of our data is now "Sensitive Personal", and some is "Sensitive Medical". We'll call these confidentiality labels, or just "labels" for short.

Now, we say that Doctors and Nurses, when they're employed by the hospital, get mandatory training in how to handle sensitive information. They're also trained - and trusted - to handle personal and medical information. We call this a "clearance".

Lab staff might only see the medical data, and other hospital staff might only see the personal - and their clearances reflect that.

You might recognise these terms from films and TV shows - "Sensitive" would be a "Classification", if that helps.

There's a number of standardized ways of handling this kind of mechanism, such as SDN.801(c) (A joint NIST/NSA private publication), STANAG 4774 (A NATO standard), and FIP-188 (A NIST public publication). I also wrote an MIT-licensed library to handle these, because I am insane and like insanely difficult problems which attract the attention of national security agencies. (Hi guys!).

These also define another element - a "Policy", which lists the classifications and tags, and tells you how they can be combined.

The Policy also adds two key features of a labelling system. Firstly, it tells you how to mark protected data. This means not only that the Doctor viewing some data is clearly informed about the sensitivity of the data, but we can also include some tags which aren't used for access control at all, and just provide information about the sensitivity of the data.

Finally, the policy tells you how to how to translate a label into someone else's policy (when, for example, you want to send a patient record to a different hospital).

When sending an email, or an instant message, people can put the right label onto the message both to ensure safety and convey the sensitivity - part of what's called "Originator Controlled Access Control", or ORCON -so messages outside the patient record are still protected.

It's a powerful system, which probably explains why it's the system used by militaries and intelligence agencies around the world to protect their data, as well as being recommended by HL7 and other healthtech standards groups for medical data.

But should any Doctor really be able to see any patient record? In the Netherlands, there was a recent scandal where a celebrity's patient records were looked at out of pure curiosity by medical staff (and others) who had no need at all.

We could combine Rule Based Access Control (RBAC) with Role Based Access Control (RBAC - yes, I know), and give things both a label and an ACL. But that's really quite painful to manage. Patients move between wards and departments as their care progresses and changes, and managing this is again going to be painful.

What if we could do this automatically, so when a patient gets transferred to a ward the ward staff automatically get the access they need?

Attribute Based Access Control

ABAC uses the data itself to derive access control decisions on the fly. Its policy is almost a programming language in its own right, digging through the data representing the Resource, Environment, and Subject to decide if the Subject can access the Resource within the Environment.

Standards such as XACML are frighteningly complex as a result, and just as Role Based Access Control can be used to implement Identity Based Access Control, XACML can be used to implement any access control system we've discussed so far, and several more we've not even thought of. Can Doctors only access Patients Records during working hours on approved equipment? Sure, we can do that.

Of course, without XACML or some similar system, we can just code the policy in more traditional programming.

The ABAC system needs to crunch a lot of data for this, of course - it needs to know if a nurse works on a particular ward, as well as if a patient is on that ward. It needs to know if a medical procedure is conducted by the same department as the consultant is working in. It needs to know if a Doctor is on-shift. It needs to know if their personal mobile phone has been approved for use.

But, if you can get by the complexity, ABAC is astonishingly powerful.

The downsides beyond complexity are more subtle. Rule Based Access Control gives a federated access control system via its translation capability - ABAC can't actually provide that. It also can't mark data, which is useful to indicate sensitivities beyond simple access control.

So what's the best access control?

Everything Based Access Control

It turns out that all access control systems have advantages and disadvantages - but handily, we can use them in combination, and that mostly removes the disadvantages.

ACLs remains the simplest solution we have for access control, especially when simplified further with roles. If you're not confident, or not able, to do anything else, just pick this.

Combine these with labels and clearances, and you've provided immediate assurance that even if the ACL says someone can read data, they still can't if they've got had the right training, or are not trusted. In addition, you have the powerful marking, so useful for human understanding, and the federated controls.

And both ACLs and Roles can be automatically assigned by code, using techniques from ABAC. Patient record updated to say they're on X Ward? Adjust the ACL automatically, and we're done. Environmental techniques from ABAC can be replicated by injecting device clearances, too.

Access Control is a complex, and vital, problem in any non-trivial system. But it's also an area that has received considerable academic study as well as numerous pragmatic approaches from industry. As with almost any big architectural decision, the best answer is "mix sensibly", the worst is "mix badly", and the safe option is to pick the easy one. But don't use Tim. He's not actually that good.