nullprogram.com/blog/2019/07/10/
tl;dr: passphrase2pgp.
One of my long-term concerns has been losing my core cryptographic keys,
or just not having access to them when I need them. I keep my important
data backed up, and if that data is private then I store it encrypted.
My keys are private, but how am I supposed to encrypt them? The chicken
or the egg?
The OpenPGP solution is to (optionally) encrypt secret keys using a key
derived from a passphrase. GnuPG prompts the user for this passphrase
when generating keys and when using secret keys. This protects the keys
at rest, and, with some caution, they can be included as part of regular
backups. The OpenPGP specification, RFC 4880 has many options
for deriving a key from this passphrase, called String-to-Key, or S2K,
algorithms. None of the options are great.
In 2012, I selected the strongest S2K configuration and,
along with a very strong passphrase, put my GnuPG keyring on the
internet as part of my public dotfiles repository. It was a
kind of super-backup that would guarantee their availability anywhere
I’d need them.
My timing was bad because, with the release of GnuPG 2.1 in 2014, GnuPG
fundamentally changed its secret keyring format. S2K options are now
(quietly!) ignored when deriving the protection keys. Instead it
auto-calibrates to much weaker settings. With this new version of GnuPG,
I could no longer update the keyring in my dotfiles repository without
significantly downgrading its protection.
By 2017 I was pretty irritated with the whole situation. I let my
OpenPGP keys expire, and then I wrote my own tool to replace
the only feature of GnuPG I was actively using: encrypting my backups
with asymmetric encryption. One of its core features is that the
asymmetric keypair can be derived from a passphrase using a memory-hard
key derivation function (KDF). Attackers must commit a significant
quantity of memory (expensive) when attempting to crack the passphrase,
making the passphrase that much more effective.
Since the asymmetric keys themselves, not just the keys protecting them,
are derived from a passphrase, I never need to back them up! They’re
also always available whenever I need them. My keys are essentially
stored entirely in my brain as if I was a character in a William
Gibson story.
Tackling OpenPGP key generation
At the time I had expressed my interest in having this feature for
OpenPGP keys. It’s something I’ve wanted for a long time. I first took
a crack at it in 2013 (now the the old-version branch) for
generating RSA keys. RSA isn’t that complicated but it’s very
easy to screw up. Since I was rolling it from scratch, I didn’t
really trust myself not to subtly get it wrong. Plus I never figured out
how to self-sign the key. GnuPG doesn’t accept secret keys that aren’t
self-signed, so it was never useful.
I took another crack at it in 2018 with a much more brute force
approach. When a program needs to generate keys, it will either read
from /dev/u?random or, on more modern systems, call getentropy(3).
These are all ultimately system calls, and I know how to intercept
those with Ptrace. If I want to control key generation for any
program, not just GnuPG, I could intercept these inputs and replace them
with the output of a CSPRNG keyed by a passphrase.
Keyed: Linux Entropy Interception
In practice this doesn’t work at all. Real programs like GnuPG and
OpenSSH’s ssh-keygen don’t rely solely on these entropy inputs. They
also grab entropy from other places, like getpid(2),
gettimeofday(2), and even extract their own scheduler and execution
time noise. Without modifying these programs I couldn’t realistically
control their key generation.
Besides, even if it did work, it would still be fragile and unreliable
since these programs could always change how they use the inputs. So,
ultimately, it was more of an experiment than something practical.
passphrase2pgp
For regular readers, it’s probably obvious that I recently learned
Go. While searching for good projects idea for cutting my teeth, I
noticed that Go’s “extended” standard library has a lot of useful
cryptographic support, so the idea of generating the keys myself may be
worth revisiting.
Something else also happened since my previous attempt: The OpenPGP
ecosystem now has widespread support for elliptic curve cryptography. So
instead of RSA, I could generate a Curve25519 keypair, which, by design,
is basically impossible to screw up. Not only would I be generating
keys on my own terms, I’d being doing it in style, baby.
There are two different ways to use Curve25519:
- Digital signatures: Ed25519 (EdDSA)
- Diffie–Hellman (encryption): X25519 (ECDH)
In GnuPG terms, the first would be a “sign only” key and the second is
an “encrypt only” key. But can’t you usually do both after you generate
a new OpenPGP key? If you’ve used GnuPG, you’ve probably seen the terms
“primary key” and “subkey”, but you probably haven’t had think about
them since it’s all usually automated.
The primary key is the one associated directly with your identity.
It’s always a signature key. The OpenPGP specification says this is a
signature key only by convention, but, practically speaking, it really
must be since signatures is what holds everything together. Like
packaging tape.
If you want to use encryption, independently generate an encryption key,
then sign that key with the primary key, binding that key as a subkey
to the primary key. This all happens automatically with GnuPG.
Fun fact: Two different primary keys can have the same subkey. Anyone
could even bind any of your subkeys to their primary key! They only need
to sign the public key! Though, of course, they couldn’t actually use
your key since they’d lack the secret key. It would just be really
confusing, and could, perhaps in certain situations, even cause some
OpenPGP clients to malfunction. (Note to self: This demands
investigation!)
It’s also possible to have signature subkeys. What good is that?
Paranoid folks will keep their primary key only on a secure, air-gapped,
then use only subkeys on regular systems. The subkeys can be revoked and
replaced independently of the primary key if something were to go wrong.
In Go, generating an X25519 key pair is this simple (yes, it actually
takes array pointers, which is rather weird):
package main
import (
"crypto/rand"
"fmt"
"golang.org/x/crypto/curve25519"
)
func main() {
var seckey, pubkey [32]byte
rand.Read(seckey[:]) // FIXME: check for error
seckey[0] &= 248
seckey[31] &= 127
seckey[31] |= 64
curve25519.ScalarBaseMult(&pubkey, &seckey)
fmt.Printf("pub %x\n", pubkey[:])
fmt.Printf("sec %x\n", seckey[:])
}
The three bitwise operations are optional since it will do these
internally, but it ensures that the secret key is in its canonical form.
The actual Diffie–Hellman exchange requires just one more function call:
curve25519.ScalarMult().
For Ed25519, the API is higher-level:
package main
import (
"crypto/rand"
"fmt"
"golang.org/x/crypto/ed25519"
)
func main() {
seed := make([]byte, ed25519.SeedSize)
rand.Read(seed) // FIXME: check for error
key := ed25519.NewKeyFromSeed(seed)
fmt.Printf("pub %x\n", key[32:])
fmt.Printf("sec %x\n", key[:32])
}
Signing a message with this key is just one function call:
ed25519.Sign().
Unfortunately that’s the easy part. The other 400 lines of the real
program are concerned only with encoding these values in the complex
OpenPGP format. That’s the hard part. GnuPG’s --list-packets option
was really useful for debugging this part.
OpenPGP specification
(Feel free to skip this section if the OpenPGP wire format isn’t
interesting to you.)
Following the specification was a real challenge, especially since many
of the details for Curve25519 only appear in still incomplete (and still
erroneous) updates to the specification. I certainly don’t envy the
people who have to parse arbitrary OpenPGP packets. It’s finicky and has
arbitrary parts that don’t seem to serve any purpose, such as redundant
prefix and suffix bytes on signature inputs. Fortunately I only had to
worry about the subset that represents an unencrypted secret key export.
OpenPGP data is broken up into packets. Each packet begins with a tag
identifying its type, followed by a length, which itself is a variable
length. All the packets produced by passphrase2pgp are short, so I could
pretend lengths were all a single byte long.
For a secret key export with one subkey, we need the following packets
in this order:
- Secret-Key: Public-Key packet with secret key appended
- User ID: just a length-prefixed, UTF-8 string
- Signature: binds Public-Key packet (1) and User ID packet (2)
- Secret-Subkey: Public-Subkey packet with secret subkey appended
- Signature: binds Public-Key packet (1) and Public-Subkey packet (4)
A Public-Key packet contains the creation date, key type, and public key
data. A Secret-Key packet is the same, but with the secret key literally
appended on the end and a different tag. The Key ID is (essentially) a
SHA-1 hash of the Public-Key packet, meaning the creation date is part
of the Key ID. That’s important for later.
I had wondered if the SHAttered attack could be used to create
two different keys with the same full Key ID. However, there’s no slack
space anywhere in the input, so I doubt it.
User IDs are usually a RFC 2822 name and email address, but that’s only
convention. It can literally be an empty string, though that wouldn’t be
useful. OpenPGP clients that require anything more than an empty string,
such as GnuPG during key generation, are adding artificial restrictions.
The first Signature packet indicates the signature date, the signature
issuer’s Key ID, and then optional metadata about how the primary key is
to be used and the capabilities the key owner’s client. The signature
itself is formed by appending the Public-Key packet portion of the
Secret-Key packet, the User ID packet, and the previously described
contents of the signature packet. The concatenation is hashed, the hash
is signed, and the signature is appended to the packet. Since the
options are included in the signature, they can’t be changed by another
person.
In theory the signature is redundant. A client could accept the
Secret-Key packet and User ID packet and consider the key imported. It
would then create its own self-signature since it has everything it
needs. However, my primary target for passphrase2pgp is GnuPG, and it
will not accept secret keys that are not self-signed.
The Secret-Subkey packet is exactly the same as the Secret-Key packet
except that it uses a different tag to indicate it’s a subkey.
The second Signature packet is constructed the same as the previous
signature packet. However, it signs the concatenation of the Public-Key
and Public-Subkey packets, binding the subkey to that primary key. This
key may similarly have its own options.
To create a public key export from this input, a client need only chop
off the secret keys and fix up the packet tags and lengths. The
signatures remain untouched since they didn’t include the secret keys.
That’s essentially what other people will receive about your key.
If someone else were to create a Signature packet binding your
Public-Subkey packet with their Public-Key packet, they could set their
own options on their version of the key. So my question is: Do clients
properly track this separate set of options and separate owner for the
same key? If not, they have a problem!
The format may not sound so complex from this description, but there are
a ton of little details that all need to be correct. To make matters
worse, the feedback is usually just a binary “valid” or “invalid”. The
world could use an OpenPGP format debugger.
Usage
There is one required argument: either --uid (-u) or --load
(-l). The former specifies a User ID since a key with an empty User ID
is pretty useless. It’s my own artificial restriction on the User ID.
The latter loads a previously-generated key which will come with a User
ID.
To generate a key for use in GnuPG, just pipe the output straight into
GnuPG:
$ passphrase2pgp --uid "Foo <foo@example.com>" | gpg --import
You will be prompted for a passphrase. That passphrase is run through
Argon2id, a memory-hard KDF, with the User ID as the salt.
Deriving the key requires 8 passes over 1GB of state, which takes my
current computers around 8 seconds. With the --paranoid (-x) option
enabled, that becomes 16 passes over 2GB (perhaps not paranoid enough?).
The output is 64 bytes: 32 bytes to seed the primary key and 32 bytes to
seed the subkey.
Despite the aggressive KDF settings, you will still need to choose a
strong passphrase. Anyone who has your public key can mount an offline
attack. A 10-word Diceware or Pokerware passphrase is more than
sufficient (~128 bits) while also being quite reasonable to memorize.
Since the User ID is the salt, an attacker couldn’t build a single
rainbow table to attack passphrases for different people. (Though your
passphrase really should be strong enough that this won’t matter!) The
cost is that you’ll need to use exactly the same User ID again to
reproduce the key. In theory you could change the User ID afterward to
whatever you like without affecting the Key ID, though it will require a
new self-signature.
The keys are not encrypted (no S2K), and there are few options you can
choose when generating the keys. If you want to change any of this, use
GnuPG’s --edit-key tool after importing. For example, to set a
protection passphrase:
$ gpg --edit-key Foo
gpg> passwd
There’s a lot that can be configured from this interface.
If you just need the public key to publish or share, the --public
(-p) option will suppress the private parts and output only a public
key. It works well in combination with ASCII armor, --armor (-a).
For example, to put your public key on the clipboard:
$ passphrase2pgp -u '...' -ap | xclip
The tool can create detached signatures (--sign, -S) entirely on its
own, too, so you don’t need to import the keys into GnuPG just to make
signatures:
$ passphrase2pgp --sign --uid '...' program.exe
This would create a file named program.exe.sig with the detached
signature, ready to be verified by another OpenPGP implementation. In
fact, you can hook it directly up to Git for signing your tags and
commits without GnuPG:
$ git config --global gpg.program passphrase2pgp
This only works for signing, and it cannot verify (verify-tag or
verify-commit).
It’s pretty tedious to enter the --uid option all the time, so, if
omitted, passphrase2pgp will infer the User ID from the environment
variables REALNAME and EMAIL. Combined with the KEYID environment
variable (see the README for details), you can easily get away with
never storing your keys: only generate them on demand when needed.
That’s how I intend to use passphrase2pgp. When I want to sign a file,
I’ll only need one option, one passphrase prompt, and a few seconds of
patience:
$ passphrase2pgp -S path/to/file
January 1, 1970
The first time you run the tool you might notice one offensive aspect of
its output: Your key will be dated January 1, 1970 — i.e. unix epoch
zero. This predates PGP itself by more than two decades, so it might
alarm people who receive your key.
Why do this? As I noted before, the creation date is part of the Key ID.
Use a different date, and, as far as OpenPGP is concerned, you have a
different key. Since users probably don’t want to remember a specific
datetime, at seconds resolution, in addition to their passphrase,
passphrase2pgp uses the same hard-coded date by default. A date of
January 1, 1970 is like NULL in a database: no data.
If you don’t like this, you can override it with the --time (-t) or
--now (-n) options, but it’s up to you to remain consistent.
Vanity Keys
If you’re interested in vanity keys — e.g. where the Key ID spells out
words or looks unusual — it wouldn’t take much work to hack up the
passphrase2pgp source into generating your preferred vanity keys. It
would easily beat anything else I could find online.
Reconsidering limited OpenPGP
Initially my intention was never to output an encryption subkey, and
passphrase2pgp would only be useful for signatures. By default it still
only produces a sign key, but you can still get an encryption subkey
with the --subkey (-s) option. I figured it might be useful to
generate an encryption key, even if it’s not output by default. Users
can always ask for it later if they have a need for it.
Why only a signing key? Nobody should be using OpenPGP for encryption
anymore. Use better tools instead and retire the 20th century
cryptography. If you don’t have an encryption subkey, nobody can
send you OpenPGP-encrypted messages.
In contrast, OpenPGP signatures are still kind of useful and lack a
practical alternative. The Web of Trust failed to reach critical mass,
but that doesn’t seem to matter much in practice. Important OpenPGP keys
can be bootstrapped off TLS by strategically publishing them on HTTPS
servers. Keybase.io has done interesting things in this area.
Further, GitHub officially supports OpenPGP signatures, and I
believe GitLab does too. This is another way to establish trust for a
key. IMHO, there’s generally too much emphasis on binding a person’s
legal identity to their OpenPGP key (e.g. the idea behind key-signing
parties). I suppose that’s useful for holding a person legally
accountable if they do something wrong. I’d prefer trust a key with has
an established history of valuable community contributions, even if done
so only under a pseudonym.
So sometime in the future I may again advertise an OpenPGP public key.
If I do, those keys would certainly be generated with passphrase2pgp. I
may not even store the secret keys on a keyring, and instead generate
them on the fly only when I occasionally need them.
nullprogram.com/blog/2019/06/30/
This article was discussed on Hacker News.
One of the frequent challenges in C is that pointers are nothing but a
memory address. A callee who is passed a pointer doesn’t truly know
anything other than the type of object being pointed at, which says some
things about alignment and how that pointer can be used… maybe. If it’s
a pointer to void (void *) then not even that much is known.
The number of consecutive elements being pointed at is also not known.
It could be as few as zero, so dereferencing would be illegal. This can
be true even when the pointer is not null. Pointers can go one past the
end of an array, at which point it points to zero elements. For example:
void foo(int *);
void bar(void)
{
int array[4];
foo(array + 4); // pointer one past the end
}
In some situations, the number of elements is known, at least to the
programmer. For example, the function might have a contract that says it
must be passed at least N elements, or exactly N elements. This
could be communicated through documentation.
/** Foo accepts 4 int values. */
void foo(int *);
Or it could be implied by the function’s prototype. Despite the
following function appearing to accept an array, that’s actually a
pointer, and the “4” isn’t relevant to the prototype.
C99 introduced a feature to make this a formal part of the prototype,
though, unfortunately, I’ve never seen a compiler actually use this
information.
void foo(int[static 4]); // >= 4 elements, cannot be null
Another common pattern is for the callee to accept a count parameter.
For example, the POSIX write() function:
ssize_t write(int fd, const void *buf, size_t count);
The necessary information describing the buffer is split across two
arguments. That can become tedious, and it’s also a source of serious
bugs if the two parameters aren’t in agreement (buffer overflow,
information disclosure, etc.). Wouldn’t it be nice if this
information was packed into the pointer itself? That’s essentially the
definition of a fat pointer.
Fat pointers via bit hacks
If we assume some things about the target platform, we can encode fat
pointers inside a plain pointer with some dirty pointer
tricks, exploiting unused bits in the pointer value. For
example, currently on x86-64, only the lower 48 bits of a pointer are
actually used. The other 16 bits could carefully be used for other
information, like communicating the number of elements or bytes:
// NOTE: x86-64 only!
unsigned char buf[1000];
uintptr addr = (uintptr_t)buf & 0xffffffffffff;
uintptr pack = (sizeof(buf) << 48) | addr;
void *fatptr = (void *)pack;
The other side can unpack this to get the components back out. Obviously
16 bits for the count will often be insufficient, so this would more
likely be used for baggy bounds checks.
Further, if we know something about the alignment — say, that it’s
16-byte aligned — then we can also encode information in the least
significant bits, such as a type tag.
Fat pointers via a struct
That’s all fragile, non-portable, and rather limited. A more robust
approach is to lift pointers up into a richer, heavier type, like a
structure.
struct fatptr {
void *ptr;
size_t len;
};
Functions accepting these fat pointers no longer need to accept a count
parameter, and they’d generally accept the fat pointer by value.
fatptr_write(int fd, struct fatptr);
In typical C implementations, the structure fields would be passed
practically, if not exactly, same way as the individual parameters would
have been passed, so it’s really no less efficient.
To help keep this straight, we might employ some macros:
#define COUNTOF(array) \
(sizeof(array) / sizeof(array[0]))
#define FATPTR(ptr, count) \
(struct fatptr){ptr, count}
#define ARRAYPTR(array) \
FATPTR(array, COUNTOF(array))
/* ... */
unsigned char buf[40];
fatptr_write(fd, ARRAYPTR(buf));
There are obvious disadvantages of this approach, like type confusion
due to that void pointer, the inability to use const, and just being
weird for C. I wouldn’t use it in a real program, but bear with me.
Before I move on, I want to add one more field to that fat pointer
struct: capacity.
struct fatptr {
void *ptr;
size_t len;
size_t cap;
};
This communicates not how many elements are present (len), but how
much additional space is left in the buffer. This allows callees know
how much room is left for, say, appending new elements.
// Fix the remainder of an int buffer with a value.
void
fill(struct fatptr ptr, int value)
{
int *buf = ptr.ptr;
for (size_t i = ptr.len; i < ptr.cap; i++) {
buf[i] = value;
}
}
Since the callee modifies the fat pointer, it should be returned:
struct fatptr
fill(struct fatptr ptr, int value)
{
int *buf = ptr.ptr;
for (size_t i = ptr.len; i < ptr.cap; i++) {
buf[i] = value;
}
ptr.len = ptr.cap;
return ptr;
}
Congratulations, you’ve got slices! Except that in Go they’re a proper
part of the language and so doesn’t rely on hazardous hacks or tedious
bookkeeping. The fatptr_write() function above nearly functionally
equivalent to the Writer.Write() method in Go, which accepts a slice:
type Writer interface {
Write(p []byte) (n int, err error)
}
The buf and count parameters are packed together as a slice, and
fd parameter is instead the receiver (the object being acted upon by
the method).
Go slices
Go famously has pointers, including internal pointers, but not pointer
arithmetic. You can take the address of (nearly) anything, but
you can’t make that pointer point at anything else, even if you took the
address of an array element. Pointer arithmetic would undermine Go’s
type safety, so it can only be done through special mechanisms in the
unsafe package.
But pointer arithmetic is really useful! It’s handy to take an address
of an array element, pass it to a function, and allow that function to
modify a slice (wink, wink) of the array. Slices are pointers that
support exactly this sort of pointer arithmetic, but safely. Unlike
the & operator which creates a simple pointer, the slice operator
derives a fat pointer.
func fill([]int, int) []int
var array [8]int
// len == 0, cap == 8, like &array[0]
fill(array[:0], 1)
// array is [1, 1, 1, 1, 1, 1, 1, 1]
// len == 0, cap == 4, like &array[4]
fill(array[4:4], 2)
// array is [1, 1, 1, 1, 2, 2, 2, 2]
The fill function could take a slice of the slice, effectively moving
the pointer around with pointer arithmetic, but without violating memory
safety due to the additional “fat pointer” information. In other words,
fat pointers can be derived from other fat pointers.
Slices aren’t as universal as pointers, at least at the moment. You can
take the address of any variable using &, but you can’t take a slice
of any variable, even if it would be logically sound.
var foo int
// attempt to make len = 1, cap = 1 slice backed by foo
var fooslice []int = foo[:] // compile-time error!
That wouldn’t be very useful anyway. However, if you really wanted to
do this, the unsafe package can accomplish it. I believe the resulting
slice would be perfectly safe to use:
// Convert to one-element array, then slice
fooslice = (*[1]int)(unsafe.Pointer(&foo))[:]
Update: Chris Siebenmann speculated about why this requires
unsafe.
Of course, slices are super flexible and have many more uses that look
less like fat pointers, but this is still how I tend to reason about
slices when I write Go.
nullprogram.com/blog/2019/05/29/
This article was discussed on Hacker News.
When designing or, in some cases, implementing a programming language
with built-in support for Unicode strings, an important decision must be
made about how to represent or encode those strings in memory. Not all
representations are equal, and there are trade-offs between different
choices.
One issue to consider is that strings typically feature random access
indexing of code points with a time complexity resembling constant
time (O(1)). However, not all string representations actually
support this well. Strings using variable length encoding, such as
UTF-8 or UTF-16, have O(n) time complexity indexing, ignoring
special cases (discussed below). The most obvious choice to achieve
O(1) time complexity — an array of 32-bit values, as in UCS-4 —
makes very inefficient use of memory, especially with typical strings.
Despite this, UTF-8 is still chosen in a number of programming
languages, or at least in their implementations. In this article I’ll
discuss three examples — Emacs Lisp, Julia, and Go — and how each takes a
slightly different approach.
Emacs Lisp
Emacs Lisp has two different types of strings that generally can be used
interchangeably: unibyte and multibyte. In fact, the difference
between them is so subtle that I bet that most people writing Emacs Lisp
don’t even realize there are two kinds of strings.
Emacs Lisp uses UTF-8 internally to encode all “multibyte” strings and
buffers. To fully support arbitrary sequences of bytes in the files
being edited, Emacs uses its own extension of Unicode to
precisely and unambiguously represent raw bytes intermixed with text.
Any arbitrary sequence of bytes can be decoded into Emacs’ internal
representation, then losslessly re-encoded back into the exact same
sequence of bytes.
Unibyte strings and buffers are really just byte-strings. In practice,
they’re essentially ISO/IEC 8859-1, a.k.a. Latin-1. It’s a Unicode
string where all code points are below 256. Emacs prefers the smallest
and simplest string representation when possible, similar to CPython
3.3+.
(multibyte-string-p "hello")
;; => nil
(multibyte-string-p "π ≈ 3.14")
;; => t
Emacs Lisp strings are mutable, and therein lies the kicker: As soon as
you insert a code point above 255, Emacs quietly converts the string to
multibyte.
(defvar fish "fish")
(multibyte-string-p fish)
;; => nil
(setf (aref fish 2) ?ŝ
(aref fish 3) ?o)
fish
;; => "fiŝo"
(multibyte-string-p fish)
;; => t
Constant time indexing into unibyte strings is straightforward, and
Emacs does the obvious thing when indexing into unibyte strings. It
helps that most strings in Emacs are probably unibyte, even when the
user isn’t working in English.
Most buffers are multibyte, even if those buffers are generally just
ASCII. Since Emacs uses gap buffers it generally doesn’t matter:
Nearly all accesses are tightly clustered around the point, so O(n)
indexing doesn’t often matter.
That leaves multibyte strings. Consider these idioms for iterating
across a string in Emacs Lisp:
(dotimes (i (length string))
(let ((c (aref string i)))
...))
(cl-loop for c being the elements of string
...)
The latter expands into essentially the same as the former: An
incrementing index that uses aref to index to that code point. So is
iterating over a multibyte string — a common operation — an O(n^2)
operation?
The good news is that, at least in this case, no! It’s essentially just
as efficient as iterating over a unibyte string. Before going over why,
consider this little puzzle. Here’s a little string comparison function
that compares two strings a code point at a time, returning their first
difference:
(defun compare (string-a string-b)
(cl-loop for a being the elements of string-a
for b being the elements of string-b
unless (eql a b)
return (cons a b)))
Let’s examine benchmarks with some long strings (100,000 code points):
(benchmark-run
(let ((a (make-string 100000 0))
(b (make-string 100000 0)))
(compare a b)))
;; => (0.012568031 0 0.0)
With using two, zeroed unibyte strings it takes 13ms. How about changing
the last code point in one of them to 256, converting it to a multibyte
string:
(benchmark-run
(let ((a (make-string 100000 0))
(b (make-string 100000 0)))
(setf (aref a (1- (length a))) 256)
(compare a b)))
;; => (0.012680513 0 0.0)
Same running time, so that multibyte string cost nothing more to iterate
across. Let’s try making them both multibyte:
(benchmark-run
(let ((a (make-string 100000 0))
(b (make-string 100000 0)))
(setf (aref a (1- (length a))) 256
(aref b (1- (length b))) 256)
(compare a b)))
;; => (2.327959762 0 0.0)
That took 2.3 seconds: about 2000x longer to run! Iterating over two
multibyte strings concurrently seems to have broken an optimization.
Can you reason about what’s happened?
To avoid the O(n) cost on this common indexing operating, Emacs keeps
a “bookmark” for the last indexing location into a multibyte string.
If the next access is nearby, it can starting looking from this
bookmark, forwards or backwards. Like a gap buffer, this gives a big
advantage to clustered accesses, including iteration.
However, this string bookmark is global, one per Emacs instance, not
once per string. In the last benchmark, the two multibyte strings are
constantly fighting over a single string bookmark, and indexing in
comparison function is reduced to O(n^2) time complexity.
So, Emacs pretends it has constant time access into its UTF-8 text
data, but it’s only faking it with some simple optimizations. This
usually works out just fine.
Julia
Another approach is to not pretend at all, and to make this limitation
of UTF-8 explicit in the interface. Julia took this approach, and it
was one of my complaints about the language. I don’t think
this is necessarily a bad choice, but I do still think it’s
inappropriate considering Julia’s target audience (i.e. Matlab users).
Julia strings are explicitly byte strings containing valid UTF-8 data.
All indexing occurs on bytes, which is trivially constant time, and
always decodes the multibyte code point starting at that byte. But
it is an error to index to a byte that doesn’t begin a code point.
That error is also trivially checked in constant time.
s = "π"
s[1]
# => 'π'
s[2]
# ERROR: UnicodeError: invalid character index
# in getindex at ./strings/basic.jl:37
Slices are still over bytes, but they “round up” to the end of the
current code point:
Iterating over a string requires helper functions which keep an internal
“bookmark” so that each access is constant time:
for i in eachindex(string)
c = string[i]
# ...
end
So Julia doesn’t pretend, it makes the problem explicit.
Go
Go is very similar to Julia, but takes an even more explicit view of
strings. All strings are byte strings and there are no restrictions on
their contents. Conventionally strings contain UTF-8 encoded text, but
this is not strictly required. There’s a unicode/utf8 package for
working with strings containing UTF-8 data.
Beyond convention, the range clause also assumes the string contains
UTF-8 data, and it’s not an error if it does not. Bytes not containing
valid UTF-8 data appear as a REPLACEMENT CHARACTER (U+FFFD).
func main() {
s := "π\xff"
for _, r := range s {
fmt.Printf("U+%04x\n", r)
}
}
// U+03c0
// U+fffd
A further case of the language favoring UTF-8 is that casting a string
to []rune decodes strings into code points, like UCS-4, again using
REPLACEMENT CHARACTER:
func main() {
s := "π\xff"
r := []rune(s)
fmt.Printf("U+%04x\n", r[0])
fmt.Printf("U+%04x\n", r[1])
}
// U+03c0
// U+fffd
So, like Julia, there’s no pretending, and the programmer explicitly
must consider the problem.
Preferences
All-in-all I probably prefer how Julia and Go are explicit with
UTF-8’s limitations, rather than Emacs Lisp’s attempt to cover it up
with an internal optimization. Since the abstraction is leaky, it may
as well be made explicit.
nullprogram.com/blog/2019/04/30/
Imagine we’re writing a C program and we need some random numbers. Maybe
it’s for a game, or for a Monte Carlo simulation, or for cryptography.
The standard library has a rand() function for some of these purposes.
There are some problems with this. Typically the implementation is a
rather poor PRNG, and we can do much better. It’s a poor choice
for Monte Carlo simulations, and outright dangerous for cryptography.
Furthermore, it’s usually a dynamic function call, which has a high
overhead compared to how little the function actually does. In
glibc, it’s also synchronized, adding even more overhead.
But, more importantly, this function returns the same sequences of
values each time the program runs. If we want different numbers each
time the program runs, it needs to be seeded — but seeded with what?
Regardless of what PRNG we ultimately use, we need inputs unique to this
particular execution.
The right places
On any modern unix-like system, the classical approach is to open
/dev/urandom and read some bytes. It’s not part of POSIX but it is a
de facto standard. These random bits are seeded from the physical
world by the operating system, making them highly unpredictable and
uncorrelated. They’re are suitable for keying a CSPRNG and, from
there, generating all the secure random bits you will ever
need (perhaps with fast-key-erasure). Why not
/dev/random? Because on Linux it’s pointlessly
superstitious, which has basically ruined that path for
everyone.
/* Returns zero on failure. */
int
getbits(void *buf, size_t len)
{
int result = 0;
FILE *f = fopen("/dev/urandom", "rb");
if (f) {
result = fread(buf, len, 1, f);
fclose(f);
}
return result;
}
int
main(void)
{
unsigned seed;
if (getbits(&seed, sizeof(seed))) {
srand(seed);
} else {
die();
}
/* ... */
}
Note how there are two different places getbits() could fail, with
multiple potential causes.
-
It could fail to open the file. Perhaps the program isn’t running on a
modern unix-like system. Perhaps it’s running in a chroot and
/dev/urandom wasn’t created. Perhaps there are too many file
descriptors already open. Perhaps there isn’t enough memory available
to open a file. Perhaps the file permissions disallow it or it’s
blocked by Mandatory Access Control (MAC).
-
It could fail to read the file. This essentially can’t happen unless
the system is severely misconfigured, in which case a successful
read would be suspect anyway. In this case it’s probably still a
good idea to check the result.
The need for creating a file descriptor a serious issue for libraries.
Libraries that quietly create and close file descriptors can interfere
with the main program, especially if its asynchronous. The main program
might rely on file descriptors being consecutive, predictable, or
monotonic (example). File descriptors are also a limited resource,
so it may exhaust a file descriptor slot needed for the main program.
For a network service, a remote attacker could perhaps open enough
sockets to deny a file descriptor to getbits(), blocking the program
from gathering entropy.
/dev/urandom is simple, but it’s not an ideal API.
getentropy(2)
Wouldn’t it be nicer if our program could just directly ask the
operating system to fill a buffer with random bits? That’s what the
OpenBSD folks thought, so they introduced a getentropy(2)
system call. When called correctly it cannot fail!
int getentropy(void *buf, size_t buflen);
Other operating systems followed suit, including Linux, though
on Linux getentropy(2) is a library function implemented using
getrandom(2), the actual system call. It’s been in the Linux
kernel since version 3.17 (October 2014), but the libc wrapper didn’t
appear in glibc until version 2.25 (February 2017). So as of this
writing, there are still many systems where it’s still not practical
to use even if their kernel is new enough.
For now on Linux you may still want to check, and have a strategy in
place, for an ENOSYS result. Some systems are still running kernels
that are 5 years old, or older.
OpenBSD also has another trick up its trick-filled sleeves: the
.openbsd.randomdata section. Just as the .bss section is
filled with zeros, the .openbsd.randomdata section is filled with
securely-generated random bits. You could put your PRNG state in this
section and it will be seeded as part of loading the program. Cool!
RtlGenRandom()
Windows doesn’t have /dev/urandom. Instead it has:
CryptGenRandom()CryptAcquireContext()CryptReleaseContext()
Though in typical Win32 fashion, the API is ugly, overly-complicated,
and has multiple possible failure points. It’s essentially impossible
to use without referencing documentation. Ugh.
However, Windows 98 and later has RtlGenRandom(),
which has a much more reasonable interface. Looks an awful lot like
getentropy(2), eh?
BOOLEAN RtlGenRandom(
PVOID RandomBuffer,
ULONG RandomBufferLength
);
The problem is that it’s not quite an official API, and no promises
are made about it. In practice, far too much software now depends on
it that the API is unlikely to ever break. Despite the prototype
above, this function is actually named SystemFunction036(), and
you have to supply your own prototype. Here’s my little drop-in
snippet that turns it nearly into getentropy(2):
#ifdef _WIN32
# define WIN32_LEAN_AND_MEAN
# include <windows.h>
# pragma comment(lib, "advapi32.lib")
BOOLEAN NTAPI SystemFunction036(PVOID, ULONG);
# define getentropy(buf, len) (SystemFunction036(buf, len) ? 0 : -1)
#endif
It works in Wine, too, where, at least in my version, it reads from
/dev/urandom.
The wrong places
That’s all well and good, but suppose we’re masochists. We want our
program to be maximally portable so we’re sticking strictly to
functionality found in the standard C library. That means no
getentropy(2) and no RtlGenRandom(). We can still try to open
/dev/urandom, but it might fail, or it might not actually be useful,
so we’ll want a backup.
The usual approach found in a thousand tutorials is time(3):
It would be better to use an integer hash function to mix up the
result from time(0) before using it as a seed. Otherwise two programs
started close in time may have similar initial sequences.
srand(triple32(time(NULL)));
The more pressing issue is that time(3) has a resolution of one
second. If the program is run twice inside of a second, they’ll both
have the same sequence of numbers. It would be better to use a higher
resolution clock, but, standard C doesn’t provide a clock with greater
than one second resolution. That normally requires calling into POSIX
or Win32.
So, we need to find some other sources of entropy unique to each
execution of the program.
Quick and dirty “string” hash function
Before we get into that, we need a way to mix these different sources
together. Here’s a small, 32-bit “string” hash function. The loop
is the same algorithm as Java’s hashCode(), and I appended my own
integer hash as a finalizer for much better diffusion.
uint32_t
hash32s(const void *buf, size_t len, uint32_t h)
{
const unsigned char *p = buf;
for (size_t i = 0; i < len; i++)
h = h * 31 + p[i];
h ^= h >> 17;
h *= UINT32_C(0xed5ad4bb);
h ^= h >> 11;
h *= UINT32_C(0xac4c1b51);
h ^= h >> 15;
h *= UINT32_C(0x31848bab);
h ^= h >> 14;
return h;
}
It accepts a starting hash value, which is essentially a “context” for
the digest that allows different inputs to be appended together. The
finalizer acts as an implicit “stop” symbol in between inputs.
I used fixed-width integers, but it could be written nearly as concisely
using only unsigned long and some masking to truncate to 32-bits. I
leave this as an exercise to the reader.
Some of the values to be mixed in will be pointers themselves. These
could instead be cast to integers and passed through an integer hash
function, but using string hash avoids various caveats. Besides,
one of the inputs will be a string, so we’ll need this function anyway.
Randomized pointers (ASLR, random stack gap, etc.)
Attackers can use predictability to their advantage, so modern systems
use unpredictability to improve security. Memory addresses for various
objects and executable code are randomized since some attacks require
an attacker to know their addresses. We can skim entropy from these
pointers to seed our PRNG.
Address Space Layout Randomization (ASLR) is when executable code and
its associated data is loaded to a random offset by the loader. Code
designed for this is called Position Independent Code (PIC). This has
long been used when loading dynamic libraries so that all of the
libraries on a system don’t have to coordinate with each other to
avoid overlapping.
To improve security, it has more recently been extended to programs
themselves. On both modern unix-like systems and Windows,
position-independent executables (PIE) are now the default.
To skim entropy from ASLR, we just need the address of one of our
functions. All the functions in our program will have the same relative
offset, so there’s no reason to use more than one. An obvious choice is
main():
uint32_t h = 0; /* initial hash value */
int (*mainptr)() = main;
h = hash32s(&mainptr, sizeof(mainptr), h);
Notice I had to store the address of main() in a variable, and then
treat the pointer itself as a buffer for the hash function? It’s not
hashing the machine code behind main, just its address. The symbol
main doesn’t store an address, so it can’t be given to the hash
function to represent its address. This is analogous to an array
versus a pointer.
On a typical x86-64 Linux system, and when this is a PIE, that’s about
3 bytes worth of entropy. On 32-bit systems, virtual memory is so
tight that it’s worth a lot less. We might want more entropy than
that, and we want to cover the case where the program isn’t compiled
as a PIE.
On unix-like systems, programs are typically dynamically linked against
the C library, libc. Each shared object gets its own ASLR offset, so we
can skim more entropy from each shared object by picking a function or
variable from each. Let’s do malloc(3) for libc ASLR:
void *(*mallocptr)() = malloc;
h = hash32s(&mallocptr, sizeof(mallocptr), h);
Allocators themselves often randomize the addresses they return so that
data objects are stored at unpredictable addresses. In particular, glibc
uses different strategies for small (brk(2)) versus big (mmap(2))
allocations. That’s two different sources of entropy:
void *small = malloc(1); /* 1 byte */
h = hash32s(&small, sizeof(small), h);
free(small);
void *big = malloc(1UL << 20); /* 1 MB */
h = hash32s(&big, sizeof(big), h);
free(big);
Finally the stack itself is often mapped at a random address, or at
least started with a random gap, so that local variable addresses are
also randomized.
void *ptr = &ptr;
h = hash32s(&ptr, sizeof(ptr), h);
Time sources
We haven’t used time(3) yet! Let’s still do that, using the full
width of time_t this time around:
time_t t = time(0);
h = hash32s(&t, sizeof(t), h);
We do have another time source to consider: clock(3). It returns an
approximation of the processor time used by the program. There’s a
tiny bit of noise and inconsistency between repeated calls. We can use
this to extract a little bit of entropy over many repeated calls.
Naively we might try to use it like this:
/* Note: don't use this */
for (int i = 0; i < 1000; i++) {
clock_t c = clock();
h = hash32s(&c, sizeof(c), h);
}
The problem is that the resolution for clock() is typically rough
enough that modern computers can execute multiple instructions between
ticks. On Windows, where CLOCKS_PER_SEC is low, that entire loop
will typically complete before the result from clock() increments
even once. With that arrangement we’re hardly getting anything from
it! So here’s a better version:
for (int i = 0; i < 1000; i++) {
unsigned long counter = 0;
clock_t start = clock();
while (clock() == start)
counter++;
h = hash32s(&start, sizeof(start), h);
h = hash32s(&counter, sizeof(counter), h);
}
The counter makes the resolution of the clock no longer important. If
it’s low resolution, then we’ll get lots of noise from the counter. If
it’s high resolution, then we get noise from the clock value itself.
Running the hash function an extra time between overall clock(3)
samples also helps with noise.
A legitimate use of tmpnam(3)
We’ve got one more source of entropy available: tmpnam(3). This
function generates a unique, temporary file name. It’s dangerous to
use as intended because it doesn’t actually create the file. There’s a
race between generating the name for the file and actually creating
it.
Fortunately we don’t actually care about the name as a filename. We’re
using this to sample entropy not directly available to us. In attempt to
get a unique name, the standard C library draws on its own sources of
entropy.
char buf[L_tmpnam] = {0};
tmpnam(buf);
h = hash32s(buf, sizeof(buf), h);
The rather unfortunately downside is that lots of modern systems produce
a linker warning when it sees tmpnam(3) being linked, even though in
this case it’s completely harmless.
So what goes into a temporary filename? It depends on the
implementation.
glibc and musl
Both get a high resolution timestamp and generate the filename directly
from the timestamp (no hashing, etc.). Unfortunately glibc does a very
poor job of also mixing getpid(2) into the timestamp before using it,
and probably makes things worse by doing so.
On these platforms, this is is a way to sample a high resolution
timestamp without calling anything non-standard.
dietlibc
In the latest release as of this writing it uses rand(3), which makes
this useless. It’s also a bug since the C library isn’t allowed to
affect the state of rand(3) outside of rand(3) and srand(3). I
submitted a bug report and this has since been fixed.
In the next release it will use a generator seeded by the ELF
AT_RANDOM value if available, or ASLR otherwise. This makes
it moderately useful.
libiberty
Generated from getpid(2) alone, with a counter to handle multiple
calls. It’s basically a way to sample the process ID without actually
calling getpid(2).
BSD libc / Bionic (Android)
Actually gathers real entropy from the operating system (via
arc4random(2)), which means we’re getting a lot of mileage out of this
one.
uclibc
Its implementation is obviously forked from glibc. However, it first
tries to read entropy from /dev/urandom, and only if that fails does
it fallback to glibc’s original high resolution clock XOR getpid(2)
method (still not hashing it).
Finishing touches
Finally, still use /dev/urandom if it’s available. This doesn’t
require us to trust that the output is anything useful since it’s just
being mixed into the other inputs.
char rnd[4];
FILE *f = fopen("/dev/urandom", "rb");
if (f) {
if (fread(rnd, sizeof(rnd), 1, f))
h = hash32s(rnd, sizeof(rnd), h);
fclose(f);
}
When we’re all done gathering entropy, set the seed from the result.
srand(h); /* or whatever you're seeding */
That’s bound to find some entropy on just about any host. Though
definitely don’t rely on the results for cryptography.
Lua
I recently tackled this problem in Lua. It has a no-batteries-included
design, demanding very little of its host platform: nothing more than an
ANSI C implementation. Because of this, a Lua program has even fewer
options for gathering entropy than C. But it’s still not impossible!
To further complicate things, Lua code is often run in a sandbox with
some features removed. For example, Lua has os.time() and os.clock()
wrapping the C equivalents, allowing for the same sorts of entropy
sampling. When run in a sandbox, os might not be available. Similarly,
io might not be available for accessing /dev/urandom.
Have you ever printed a table, though? Or a function? It evaluates to
a string containing the object’s address.
$ lua -e 'print(math)'
table: 0x559577668a30
$ lua -e 'print(math)'
table: 0x55e4a3679a30
Since the raw pointer values are leaked to Lua, we can skim allocator
entropy like before. Here’s the same hash function in Lua 5.3:
local function hash32s(buf, h)
for i = 1, #buf do
h = h * 31 + buf:byte(i)
end
h = h & 0xffffffff
h = h ~ (h >> 17)
h = h * 0xed5ad4bb
h = h & 0xffffffff
h = h ~ (h >> 11)
h = h * 0xac4c1b51
h = h & 0xffffffff
h = h ~ (h >> 15)
h = h * 0x31848bab
h = h & 0xffffffff
h = h ~ (h >> 14)
return h
end
Now hash a bunch of pointers in the global environment:
local h = hash32s({}, 0) -- hash a new table
for varname, value in pairs(_G) do
h = hash32s(varname, h)
h = hash32s(tostring(value), h)
if type(value) == 'table' then
for k, v in pairs(value) do
h = hash32s(tostring(k), h)
h = hash32s(tostring(v), h)
end
end
end
math.randomseed(h)
Unfortunately this doesn’t actually work well on one platform I tested:
Cygwin. Cygwin has few security features, notably lacking ASLR, and
having a largely deterministic allocator.
When to use it
In practice it’s not really necessary to use these sorts of tricks of
gathering entropy from odd places. It’s something that comes up more
in coding challenges and exercises than in real programs. I’m probably
already making platform-specific calls in programs substantial enough
to need it anyway.
On a few occasions I have thought about these things when debugging.
ASLR makes return pointers on the stack slightly randomized on each
run, which can change the behavior of some kinds of bugs. Allocator
and stack randomization does similar things to most of your pointers.
GDB tries to disable some of these features during debugging, but it
doesn’t get everything.
nullprogram.com/blog/2019/03/28/
This article was discussed on Hacker News.
The Windows API — a.k.a. Win32 — is notorious for being clunky, ugly,
and lacking good taste. Microsoft has done a pretty commendable job with
backwards compatibility, but the trade-off is that the API is filled to
the brim with historical cruft. Every hasty, poor design over the
decades is carried forward forever, and, in many cases, even built upon,
which essentially doubles down on past mistakes. POSIX certainly has its
own ugly corners, but those are the exceptions. In the Windows API,
elegance is the exception.
That’s why, when I recently revisited the Fibers API, I was
pleasantly surprised. It’s one of the exceptions — much cleaner than the
optional, deprecated, and now obsolete POSIX equivalent. It’s
not quite an apples-to-apples comparison since the POSIX version is
slightly more powerful, and more complicated as a result. I’ll cover the
difference in this article.
For the last part of this article, I’ll walk through an async/await
framework build on top of fibers. The framework allows coroutines in C
programs to await on arbitrary kernel objects.
Fiber Async/await Demo
Fibers
Windows fibers are really just stackful, symmetric coroutines.
From a different point of view, they’re cooperatively scheduled threads,
which is the source of the analogous name, fibers. They’re symmetric
because all fibers are equal, and no fiber is the “main” fiber. If any
fiber returns from its start routine, the program exits. (Older versions
of Wine will crash when this happens, but it was recently fixed.) It’s
equivalent to the process’ main thread returning from main(). The
initial fiber is free to create a second fiber, yield to it, then the
second fiber destroys the first.
For now I’m going to focus on the core set of fiber functions. There are
some additional capabilities I’m going to ignore, including support for
fiber local storage. The important functions are just these five:
void *CreateFiber(size_t stack_size, void (*proc)(void *), void *arg);
void SwitchToFiber(void *fiber);
bool ConvertFiberToThread(void);
void *ConvertThreadToFiber(void *arg);
void DeleteFiber(void *fiber);
To emphasize its simplicity, I’ve shown them here with more standard
prototypes than seen in their formal documentation. That documentation
uses the clunky Windows API typedefs still burdened with its 16-bit
heritage — e.g. LPVOID being a “long pointer” from the segmented memory
of the 8086:
Fibers are represented using opaque, void pointers. Maybe that’s a little
too simple since it’s easy to misuse in C, but I like it. The return
values for CreateFiber() and ConvertThreadToFiber() are void pointers
since these both create fibers.
The fiber start routine returns nothing and takes a void “user pointer”.
That’s nearly what I’d expect, except that it would probably make more
sense for a fiber to return int, which is more in line with
main / WinMain / mainCRTStartup / WinMainCRTStartup. As I said,
when any fiber returns from its start routine, it’s like returning from
the main function, so it should probably have returned an integer.
A fiber may delete itself, which is the same as exiting the thread.
However, a fiber cannot yield (e.g. SwitchToFiber()) to itself. That’s
undefined behavior.
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
void
coup(void *king)
{
puts("Long live the king!");
DeleteFiber(king);
ConvertFiberToThread(); /* seize the main thread */
/* ... */
}
int
main(void)
{
void *king = ConvertThreadToFiber(0);
void *pretender = CreateFiber(0, coup, king);
SwitchToFiber(pretender);
abort(); /* unreachable */
}
Only fibers can yield to fibers, but when the program starts up, there
are no fibers. At least one thread must first convert itself into a
fiber using ConvertThreadToFiber(), which returns the fiber object
that represents itself. It takes one argument analogous to the last
argument of CreateFiber(), except that there’s no start routine to
accept it. The process is reversed with ConvertFiberToThread().
Fibers don’t belong to any particular thread and can be scheduled on any
thread if properly synchronized. Obviously one should never yield to the
same fiber in two different threads at the same time.
Contrast with POSIX
The equivalent POSIX systems was context switching. It’s also stackful
and symmetric, but it has just three important functions:
getcontext(3), makecontext(3), and
swapcontext.
int getcontext(ucontext_t *ucp);
void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...);
int swapcontext(ucontext_t *oucp, const ucontext_t *ucp);
These are roughly equivalent to GetCurrentFiber(),
CreateFiber(), and SwitchToFiber(). There is no need for
ConvertFiberToThread() since threads can context switch without
preparation. There’s also no DeleteFiber() because the resources are
managed by the program itself. That’s where POSIX contexts are a little
bit more powerful.
The first argument to CreateFiber() is the desired stack size, with
zero indicating the default stack size. The stack is allocated and freed
by the operating system. The downside is that the caller doesn’t have a
choice in managing the lifetime of this stack and how it’s allocated. If
you’re frequently creating and destroying coroutines, those stacks are
constantly being allocated and freed.
In makecontext(3), the caller allocates and supplies the stack. Freeing
that stack is equivalent to destroying the context. A program that
frequently creates and destroys contexts can maintain a stack pool or
otherwise more efficiently manage their allocation. This makes it more
powerful, but it also makes it a little more complicated. It would be hard
to remember how to do all this without a careful reading of the
documentation:
/* Create a context */
ucontext_t ctx;
ctx.uc_stack.ss_sp = malloc(SIGSTKSZ);
ctx.uc_stack.ss_size = SIGSTKSZ;
ctx.uc_link = 0;
getcontext(&ctx);
makecontext(&ctx, proc, 0);
/* Destroy a context */
free(ctx.uc_stack.ss_sp);
Note how makecontext(3) is variadic (...), passing its arguments on
to the start routine of the context. This seems like it might be better
than a user pointer. Unfortunately it’s not, since those arguments are
strictly limited to integers.
Ultimately I like the fiber API better. The first time I tried it out, I
could guess my way through it without looking closely at the
documentation.
Async / await with fibers
Why was I looking at the Fiber API? I’ve known about coroutines for
years but I didn’t understand how they could be useful. Sure, the
function can yield, but what other coroutine should it yield to? It
wasn’t until I was recently bit by the async/await bug that I
finally saw a “killer feature” that justified their use. Generators come
pretty close, though.
Windows fibers are a coroutine primitive suitable for async/await in C
programs, where it can also be useful. To prove that it’s
possible, I built async/await on top of fibers in 95 lines of code.
The alternatives are to use a third-party coroutine library or to
do it myself with some assembly programming. However, having it
built into the operating system is quite convenient! It’s unfortunate
that it’s limited to Windows. Ironically, though, everything I wrote for
this article, including the async/await demonstration, was originally
written on Linux using Mingw-w64 and tested using Wine. Only
after I was done did I even try it on Windows.
Before diving into how it works, there’s a general concept about the
Windows API that must be understood: All kernel objects can be in
either a signaled or unsignaled state. The API provides functions that
block on a kernel object until it is signaled. The two important ones
are WaitForSingleObject() and WaitForMultipleObjects().
The latter behaves very much like poll(2) in POSIX.
Usually the signal is tied to some useful event, like a process or
thread exiting, the completion of an I/O operation (i.e. asynchronous
overlapped I/O), a semaphore being incremented, etc. It’s a generic way
to wait for some event. However, instead of blocking the thread,
wouldn’t it be nice to await on the kernel object? In my aio
library for Emacs, the fundamental “wait” object was a promise. For this
API it’s a kernel object handle.
So, the await function will take a kernel object, register it with the
scheduler, then yield to the scheduler. The scheduler — which is a
global variable, so there’s only one scheduler per process — looks like
this:
struct {
void *main_fiber;
HANDLE handles[MAXIMUM_WAIT_OBJECTS];
void *fibers[MAXIMUM_WAIT_OBJECTS];
void *dead_fiber;
int count;
} async_loop;
While fibers are symmetric, coroutines in my async/await implementation
are not. One fiber is the scheduler, main_fiber, and the other fibers
always yield to it.
There is an array of kernel object handles, handles, and an array of
fibers. The elements in these arrays are paired with each other, but
it’s convenient to store them separately, as I’ll show soon. fibers[0]
is waiting on handles[0], and so on.
The array is a fixed size, MAXIMUM_WAIT_OBJECTS (64), because there’s
a hard limit on the number of fibers that can wait at once. This
pathetically small limitation is an unfortunate, hard-coded restriction
of the Windows API. It kills most practical uses of my little library.
Fortunately there’s no limit on the number of handles we might want to
wait on, just the number of co-existing fibers.
When a fiber is about to return from its start routine, it yields one
last time and registers itself on the dead_fiber member. The scheduler
will delete this fiber as soon as it’s given control. Fibers never
truly return since that would terminate the program.
With this, the await function, async_await(), is pretty simple. It
registers the handle with the scheduler, then yields to the scheduler
fiber.
void
async_await(HANDLE h)
{
async_loop.handles[async_loop.count] = h;
async_loop.fibers[async_loop.count] = GetCurrentFiber();
async_loop.count++;
SwitchToFiber(async_loop.main_fiber);
}
Caveat: The scheduler destroys this handle with CloseHandle() after it
signals, so don’t try to reuse it. This made my demonstration simpler,
but it might be better to not do this.
A fiber can exit at any time. Such an exit is inserted implicitly before
a fiber actually returns:
void
async_exit(void)
{
async_loop.dead_fiber = GetCurrentFiber();
SwitchToFiber(async_loop.main_fiber);
}
The start routine given to async_start() is actually wrapped in the
real start routine. This is how async_exit() is injected:
struct fiber_wrapper {
void (*func)(void *);
void *arg;
};
static void
fiber_wrapper(void *arg)
{
struct fiber_wrapper *fw = arg;
fw->func(fw->arg);
async_exit();
}
int
async_start(void (*func)(void *), void *arg)
{
if (async_loop.count == MAXIMUM_WAIT_OBJECTS) {
return 0;
} else {
struct fiber_wrapper fw = {func, arg};
SwitchToFiber(CreateFiber(0, fiber_wrapper, &fw));
return 1;
}
}
The library provides a single awaitable function, async_sleep(). It
creates a “waitable timer” object, starts the countdown, and returns it.
(Notice how SetWaitableTimer() is a typically-ugly Win32 function with
excessive parameters.)
HANDLE
async_sleep(double seconds)
{
HANDLE promise = CreateWaitableTimer(0, 0, 0);
LARGE_INTEGER t;
t.QuadPart = (long long)(seconds * -10000000.0);
SetWaitableTimer(promise, &t, 0, 0, 0, 0);
return promise;
}
A more realistic example would be overlapped I/O. For example, you’d
open a file (CreateFile()) in overlapped mode, then when you, say,
read from that file (ReadFile()) you create an event object
(CreateEvent()), populate an overlapped I/O structure with the event,
offset, and length, then finally await on the event object. The fiber
will be resumed when the operation is complete.
Side note: Unfortunately overlapped I/O doesn’t work correctly for
files, and many operations can’t be done asynchronously, like
opening files. When it comes to files, you’re better off using
dedicated threads as libuv does instead of overlapped I/O.
You can still await on these operations. You’d just await on the signal
from the thread doing synchronous I/O, not from overlapped I/O.
The most complex part is the scheduler, and it’s really not complex at
all:
void
async_run(void)
{
while (async_loop.count) {
/* Wait for next event */
DWORD nhandles = async_loop.count;
HANDLE *handles = async_loop.handles;
DWORD r = WaitForMultipleObjects(nhandles, handles, 0, INFINITE);
/* Remove event and fiber from waiting array */
void *fiber = async_loop.fibers[r];
CloseHandle(async_loop.handles[r]);
async_loop.handles[r] = async_loop.handles[nhandles - 1];
async_loop.fibers[r] = async_loop.fibers[nhandles - 1];
async_loop.count--;
/* Run the fiber */
SwitchToFiber(fiber);
/* Destroy the fiber if it exited */
if (async_loop.dead_fiber) {
DeleteFiber(async_loop.dead_fiber);
async_loop.dead_fiber = 0;
}
}
}
This is why the handles are in their own array. The array can be passed
directly to WaitForMultipleObjects(). The return value indicates which
handle was signaled. The handle is closed, the entry removed from the
scheduler, and then the fiber is resumed.
That WaitForMultipleObjects() is what limits the number of fibers.
It’s not possible to wait on more than 64 handles at once! This is
hard-coded into the API. How? A return value of 64 is an error code, and
changing this would break the API. Remember what I said about being
locked into bad design decisions of the past?
To be fair, WaitForMultipleObjects() was a doomed API anyway, just
like select(2) and poll(2) in POSIX. It scales very poorly since the
entire array of objects being waited on must be traversed on each call.
That’s terribly inefficient when waiting on large numbers of objects.
This sort of problem is solved by interfaces like kqueue (BSD), epoll
(Linux), and IOCP (Windows). Unfortunately IOCP doesn’t really fit this
particular problem well — awaiting on kernel objects — so I
couldn’t use it.
When the awaiting fiber count is zero and the scheduler has control, all
fibers must have completed and there’s nothing left to do. However, the
caller can schedule more fibers and then restart the scheduler if
desired.
That’s all there is to it. Have a look at demo.c to see how
the API looks in some trivial examples. On Linux you can see it in
action with make check. On Windows, you just need to compile
it, then run it like a normal program. If there was a better
function than WaitForMultipleObjects() in the Windows API, I would
have considered turning this demonstration into a real library.
nullprogram.com/blog/2019/03/22/
This article was discussed on Hacker News, on reddit
(also), and featured in BSD Now 294.
I’m a big fan of tarpits: a network service that intentionally inserts
delays in its protocol, slowing down clients by forcing them to wait.
This arrests the speed at which a bad actor can attack or probe the
host system, and it ties up some of the attacker’s resources that
might otherwise be spent attacking another host. When done well, a
tarpit imposes more cost on the attacker than the defender.
The Internet is a very hostile place, and anyone who’s ever stood up
an Internet-facing IPv4 host has witnessed the immediate and
continuous attacks against their server. I’ve maintained such a
server for nearly six years now, and more than 99% of my
incoming traffic has ill intent. One part of my defenses has been
tarpits in various forms. The latest addition is an SSH tarpit I wrote
a couple of months ago:
Endlessh: an SSH tarpit
This program opens a socket and pretends to be an SSH server. However,
it actually just ties up SSH clients with false promises indefinitely
— or at least until the client eventually gives up. After cloning the
repository, here’s how you can try it out for yourself (default port
2222):
$ make
$ ./endlessh &
$ ssh -p2222 localhost
Your SSH client will hang there and wait for at least several days
before finally giving up. Like a mammoth in the La Brea Tar Pits, it
got itself stuck and can’t get itself out. As I write, my
Internet-facing SSH tarpit currently has 27 clients trapped in it. A
few of these have been connected for weeks. In one particular spike it
had 1,378 clients trapped at once, lasting about 20 hours.
My Internet-facing Endlessh server listens on port 22, which is the
standard SSH port. I long ago moved my real SSH server off to another
port where it sees a whole lot less SSH traffic — essentially none.
This makes the logs a whole lot more manageable. And (hopefully)
Endlessh convinces attackers not to look around for an SSH server on
another port.
How does it work? Endlessh exploits a little paragraph in RFC
4253, the SSH protocol specification. Immediately after the TCP
connection is established, and before negotiating the cryptography,
both ends send an identification string:
SSH-protoversion-softwareversion SP comments CR LF
The RFC also notes:
The server MAY send other lines of data before sending the version
string.
There is no limit on the number of lines, just that these lines must
not begin with “SSH-“ since that would be ambiguous with the
identification string, and lines must not be longer than 255
characters including CRLF. So Endlessh sends and endless stream of
randomly-generated “other lines of data” without ever intending to
send a version string. By default it waits 10 seconds between each
line. This slows down the protocol, but prevents it from actually
timing out.
This means Endlessh need not know anything about cryptography or the
vast majority of the SSH protocol. It’s dead simple.
Implementation strategies
Ideally the tarpit’s resource footprint should be as small as
possible. It’s just a security tool, and the server does have an
actual purpose that doesn’t include being a tarpit. It should tie up
the attacker’s resources, not the server’s, and should generally be
unnoticeable. (Take note all those who write the awful “security”
products I have to tolerate at my day job.)
Even when many clients have been trapped, Endlessh spends more than
99.999% of its time waiting around, doing nothing. It wouldn’t even be
accurate to call it I/O-bound. If anything, it’s timer-bound,
waiting around before sending off the next line of data. The most
precious resource to conserve is memory.
Processes
The most straightforward way to implement something like Endlessh is a
fork server: accept a connection, fork, and the child simply alternates
between sleep(3) and write(2):
for (;;) {
ssize_t r;
char line[256];
sleep(DELAY);
generate_line(line);
r = write(fd, line, strlen(line));
if (r == -1 && errno != EINTR) {
exit(0);
}
}
A process per connection is a lot of overhead when connections are
expected to be up hours or even weeks at a time. An attacker who knows
about this could exhaust the server’s resources with little effort by
opening up lots of connections.
Threads
A better option is, instead of processes, to create a thread per
connection. On Linux this is practically the same thing, but it’s
still better. However, you still have to allocate a stack for the thread
and the kernel will have to spend some resources managing the thread.
Poll
For Endlessh I went for an even more lightweight version: a
single-threaded poll(2) server, analogous to stackless green threads.
The overhead per connection is about as low as it gets.
Clients that are being delayed are not registered in poll(2). Their
only overhead is the socket object in the kernel, and another 78 bytes
to track them in Endlessh. Most of those bytes are used only for
accurate logging. Only those clients that are overdue for a new line
are registered for poll(2).
When clients are waiting, but no clients are overdue, poll(2) is
essentially used in place of sleep(3). Though since it still needs
to manage the accept server socket, it (almost) never actually waits
on nothing.
There’s an option to limit the total number of client connections so
that it doesn’t get out of hand. In this case it will stop polling the
accept socket until a client disconnects. I probably shouldn’t have
bothered with this option and instead relied on ulimit, a feature
already provided by the operating system.
I could have used epoll (Linux) or kqueue (BSD), which would be much
more efficient than poll(2). The problem with poll(2) is that it’s
constantly registering and unregistering Endlessh on each of the
overdue sockets each time around the main loop. This is by far the
most CPU-intensive part of Endlessh, and it’s all inflicted on the
kernel. Most of the time, even with thousands of clients trapped in
the tarpit, only a small number of them at polled at once, so I opted
for better portability instead.
One consequence of not polling connections that are waiting is that
disconnections aren’t noticed in a timely fashion. This makes the logs
less accurate than I like, but otherwise it’s pretty harmless.
Unforunately even if I wanted to fix this, the poll(2) interface
isn’t quite equipped for it anyway.
Raw sockets
With a poll(2) server, the biggest overhead remaining is in the
kernel, where it allocates send and receive buffers for each client
and manages the proper TCP state. The next step to reducing this
overhead is Endlessh opening a raw socket and speaking TCP itself,
bypassing most of the operating system’s TCP/IP stack.
Much of the TCP connection state doesn’t matter to Endlessh and doesn’t
need to be tracked. For example, it doesn’t care about any data sent by
the client, so no receive buffer is needed, and any data that arrives
could be dropped on the floor.
Even more, raw sockets would allow for some even nastier tarpit tricks.
Despite the long delays between data lines, the kernel itself responds
very quickly on the TCP layer and below. ACKs are sent back quickly and
so on. An astute attacker could detect that the delay is artificial,
imposed above the TCP layer by an application.
If Endlessh worked at the TCP layer, it could tarpit the TCP protocol
itself. It could introduce artificial “noise” to the connection
that requires packet retransmissions, delay ACKs, etc. It would look a
lot more like network problems than a tarpit.
I haven’t taken Endlessh this far, nor do I plan to do so. At the
moment attackers either have a hard timeout, so this wouldn’t matter,
or they’re pretty dumb and Endlessh already works well enough.
asyncio and other tarpits
Since writing Endless I’ve learned about Python’s asycio, and
it’s actually a near perfect fit for this problem. I should have just
used it in the first place. The hard part is already implemented within
asyncio, and the problem isn’t CPU-bound, so being written in Python
doesn’t matter.
Here’s a simplified (no logging, no configuration, etc.) version of
Endlessh implemented in about 20 lines of Python 3.7:
import asyncio
import random
async def handler(_reader, writer):
try:
while True:
await asyncio.sleep(10)
writer.write(b'%x\r\n' % random.randint(0, 2**32))
await writer.drain()
except ConnectionResetError:
pass
async def main():
server = await asyncio.start_server(handler, '0.0.0.0', 2222)
async with server:
await server.serve_forever()
asyncio.run(main())
Since Python coroutines are stackless, the per-connection memory
overhead is comparable to the C version. So it seems asycio is
perfectly suited for writing tarpits! Here’s an HTTP tarpit to trip up
attackers trying to exploit HTTP servers. It slowly sends a random,
endless HTTP header:
import asyncio
import random
async def handler(_reader, writer):
writer.write(b'HTTP/1.1 200 OK\r\n')
try:
while True:
await asyncio.sleep(5)
header = random.randint(0, 2**32)
value = random.randint(0, 2**32)
writer.write(b'X-%x: %x\r\n' % (header, value))
await writer.drain()
except ConnectionResetError:
pass
async def main():
server = await asyncio.start_server(handler, '0.0.0.0', 8080)
async with server:
await server.serve_forever()
asyncio.run(main())
Try it out for yourself. Firefox and Chrome will spin on that server
for hours before giving up. I have yet to see curl actually timeout on
its own in the default settings (--max-time/-m does work
correctly, though).
Parting exercise for the reader: Using the examples above as a starting
point, implement an SMTP tarpit using asyncio. Bonus points for using
TLS connections and testing it against real spammers.
nullprogram.com/blog/2019/03/10/
As part of building my Python proficiency, I’ve learned how to
use asyncio. This new language feature first appeared in
Python 3.5 (PEP 492, September 2015). JavaScript grew a
nearly identical feature in ES2017 (June 2017). An async function
can pause to await on an asynchronously computed result, much like a
generator pausing when it yields a value.
In fact, both Python and JavaScript async functions are essentially just
fancy generator functions with some specialized syntax and semantics.
That is, they’re stackless coroutines. Both languages already had
generators, so their generator-like async functions are a natural
extension that — unlike stackful coroutines — do not require
significant, new runtime plumbing.
Emacs officially got generators in 25.1 (September 2016),
though, unlike Python and JavaScript, it didn’t require any additional
support from the compiler or runtime. It’s implemented entirely using
Lisp macros. In other words, it’s just another library, not a core
language feature. In theory, the generator library could be easily
backported to the first Emacs release to properly support lexical
closures, Emacs 24.1 (June 2012).
For the same reason, stackless async/await coroutines can also be
implemented as a library. So that’s what I did, letting Emacs’ generator
library do most of the heavy lifting. The package is called aio:
It’s modeled more closely on JavaScript’s async functions than Python’s
asyncio, with the core representation being promises rather than a
coroutine objects. I just have an easier time reasoning about promises
than coroutines.
I’m definitely not the first person to realize this was
possible, and was beaten to the punch by two years. Wanting to
avoid fragmentation, I set aside all formality in my first
iteration on the idea, not even bothering with namespacing my
identifiers. It was to be only an educational exercise. However, I got
quite attached to my little toy. Once I got my head wrapped around the
problem, everything just sort of clicked into place so nicely.
In this article I will show step-by-step one way to build async/await
on top of generators, laying out one concept at a time and then
building upon each. But first, some examples to illustrate the desired
final result.
aio example
Ignoring all its problems for a moment, suppose you want to use
url-retrieve to fetch some content from a URL and return it. To keep
this simple, I’m going to omit error handling. Also assume that
lexical-binding is t for all examples. Besides, lexical scope
required by the generator library, and therefore also required by aio.
The most naive approach is to fetch the content synchronously:
(defun fetch-fortune-1 (url)
(let ((buffer (url-retrieve-synchronously url)))
(with-current-buffer buffer
(prog1 (buffer-string)
(kill-buffer)))))
The result is returned directly, and errors are communicated by an error
signal (e.g. Emacs’ version of exceptions). This is convenient, but the
function will block the main thread, locking up Emacs until the result
has arrived. This is obviously very undesirable, so, in practice,
everyone nearly always uses the asynchronous version:
(defun fetch-fortune-2 (url callback)
(url-retrieve url (lambda (_status)
(funcall callback (buffer-string)))))
The main thread no longer blocks, but it’s a whole lot less
convenient. The result isn’t returned to the caller, and instead the
caller supplies a callback function. The result, whether success or
failure, will be delivered via callback, so the caller must split
itself into two pieces: the part before the callback and the callback
itself. Errors cannot be delivered using a error signal because of the
inverted flow control.
The situation gets worse if, say, you need to fetch results from two
different URLs. You either fetch results one at a time (inefficient),
or you manage two different callbacks that could be invoked in any
order, and therefore have to coordinate.
Wouldn’t it be nice for the function to work like the first example,
but be asynchronous like the second example? Enter async/await:
(aio-defun fetch-fortune-3 (url)
(let ((buffer (aio-await (aio-url-retrieve url))))
(with-current-buffer buffer
(prog1 (buffer-string)
(kill-buffer)))))
A function defined with aio-defun is just like defun except that
it can use aio-await to pause and wait on any other function defined
with aio-defun — or, more specifically, any function that returns a
promise. Borrowing Python parlance: Returning a promise makes a
function awaitable. If there’s an error, it’s delivered as a error
signal from aio-url-retrieve, just like the first example. When
called, this function returns immediately with a promise object that
represents a future result. The caller might look like this:
(defcustom fortune-url ...)
(aio-defun display-fortune ()
(interactive)
(message "%s" (aio-await (fetch-fortune-3 fortune-url))))
How wonderfully clean that looks! And, yes, it even works with
interactive like that. I can M-x display-fortune and a fortune is
printed in the minibuffer as soon as the result arrives from the
server. In the meantime Emacs doesn’t block and I can continue my
work.
You can’t do anything you couldn’t already do before. It’s just a
nicer way to organize the same callbacks: implicit rather than
explicit.
Promises, simplified
The core object at play is the promise. Promises are already a
rather simple concept, but aio promises have been distilled to their
essence, as they’re only needed for this singular purpose. More on
this later.
As I said, a promise represents a future result. In practical terms, a
promise is just an object to which one can subscribe with a callback.
When the result is ready, the callbacks are invoked. Another way to
put it is that promises reify the concept of callbacks. A
callback is no longer just the idea of extra argument on a function.
It’s a first-class thing that itself can be passed around as a
value.
Promises have two slots: the final promise result and a list of
subscribers. A nil result means the result hasn’t been computed
yet. It’s so simple I’m not even bothering with cl-struct.
(defun aio-promise ()
"Create a new promise object."
(record 'aio-promise nil ()))
(defsubst aio-promise-p (object)
(and (eq 'aio-promise (type-of object))
(= 3 (length object))))
(defsubst aio-result (promise)
(aref promise 1))
To subscribe to a promise, use aio-listen:
(defun aio-listen (promise callback)
(let ((result (aio-result promise)))
(if result
(run-at-time 0 nil callback result)
(push callback (aref promise 2)))))
If the result isn’t ready yet, add the callback to the list of
subscribers. If the result is ready call the callback in the next
event loop turn using run-at-time. This is important because it
keeps all the asynchronous components isolated from one another. They
won’t see each others’ frames on the call stack, nor frames from
aio. This is so important that the Promises/A+ specification
is explicit about it.
The other half of the equation is resolving a promise, which is done
with aio-resolve. Unlike other promises, aio promises don’t care
whether the promise is being fulfilled (success) or rejected
(error). Instead a promise is resolved using a value function — or,
usually, a value closure. Subscribers receive this value function
and extract the value by invoking it with no arguments.
Why? This lets the promise’s resolver decide the semantics of the
result. Instead of returning a value, this function can instead signal
an error, propagating an error signal that terminated an async function.
Because of this, the promise doesn’t need to know how it’s being
resolved.
When a promise is resolved, subscribers are each scheduled in their own
event loop turns in the same order that they subscribed. If a promise
has already been resolved, nothing happens. (Thought: Perhaps this
should be an error in order to catch API misuse?)
(defun aio-resolve (promise value-function)
(unless (aio-result promise)
(let ((callbacks (nreverse (aref promise 2))))
(setf (aref promise 1) value-function
(aref promise 2) ())
(dolist (callback callbacks)
(run-at-time 0 nil callback value-function)))))
If you’re not an async function, you might subscribe to a promise like
so:
(aio-listen promise (lambda (v)
(message "%s" (funcall v))))
The simplest example of a non-async function that creates and delivers
on a promise is a “sleep” function:
(defun aio-sleep (seconds &optional result)
(let ((promise (aio-promise))
(value-function (lambda () result)))
(prog1 promise
(run-at-time seconds nil
#'aio-resolve promise value-function))))
Similarly, here’s a “timeout” promise that delivers a special timeout
error signal at a given time in the future.
(defun aio-timeout (seconds)
(let ((promise (aio-promise))
(value-function (lambda () (signal 'aio-timeout nil))))
(prog1 promise
(run-at-time seconds nil
#'aio-resolve promise value-function))))
That’s all there is to promises.
Evaluate in the context of a promise
Before we get into pausing functions, lets deal with the slightly
simpler matter of delivering their return values using a promise. What
we need is a way to evaluate a “body” and capture its result in a
promise. If the body exits due to a signal, we want to capture that as
well.
Here’s a macro that does just this:
(defmacro aio-with-promise (promise &rest body)
`(aio-resolve ,promise
(condition-case error
(let ((result (progn ,@body)))
(lambda () result))
(error (lambda ()
(signal (car error) ; rethrow
(cdr error)))))))
The body result is captured in a closure and delivered to the promise.
If there’s an error signal, it’s “rethrown” into subscribers by the
promise’s value function.
This is where Emacs Lisp has a serious weak spot. There’s not really a
concept of rethrowing a signal. Unlike a language with explicit
exception objects that can capture a snapshot of the backtrace, the
original backtrace is completely lost where the signal is caught.
There’s no way to “reattach” it to the signal when it’s rethrown. This
is unfortunate because it would greatly help debugging if you got to see
the full backtrace on the other side of the promise.
Async functions
So we have promises and we want to pause a function on a promise.
Generators have iter-yield for pausing an iterator’s execution. To
tackle this problem:
- Yield the promise to pause the iterator.
- Subscribe a callback on the promise that continues the generator
(
iter-next) with the promise’s result as the yield result.
All the hard work is done in either side of the yield, so aio-await is
just a simple wrapper around iter-yield:
(defmacro aio-await (expr)
`(funcall (iter-yield ,expr)))
Remember, that funcall is here to extract the promise value from the
value function. If it signals an error, this propagates directly into
the iterator just as if it had been a direct call — minus an accurate
backtrace.
So aio-lambda / aio-defun needs to wrap the body in a generator
(iter-lamba), invoke it to produce a generator, then drive the
generator using callbacks. Here’s a simplified, unhygienic definition of
aio-lambda:
(defmacro aio-lambda (arglist &rest body)
`(lambda (&rest args)
(let ((promise (aio-promise))
(iter (apply (iter-lambda ,arglist
(aio-with-promise promise
,@body))
args)))
(prog1 promise
(aio--step iter promise nil)))))
The body is evaluated inside aio-with-promise with the result
delivered to the promise returned directly by the async function.
Before returning, the iterator is handed to aio--step, which drives
the iterator forward until it delivers its first promise. When the
iterator yields a promise, aio--step attaches a callback back to
itself on the promise as described above. Immediately driving the
iterator up to the first yielded promise “primes” it, which is
important for getting the ball rolling on any asynchronous operations.
If the iterator ever yields something other than a promise, it’s
delivered right back into the iterator.
(defun aio--step (iter promise yield-result)
(condition-case _
(cl-loop for result = (iter-next iter yield-result)
then (iter-next iter (lambda () result))
until (aio-promise-p result)
finally (aio-listen result
(lambda (value)
(aio--step iter promise value))))
(iter-end-of-sequence)))
When the iterator is done, nothing more needs to happen since the
iterator resolves its own return value promise.
The definition of aio-defun just uses aio-lambda with defalias.
There’s nothing to it.
That’s everything you need! Everything else in the package is merely
useful, awaitable functions like aio-sleep and aio-timeout.
Composing promises
Unfortunately url-retrieve doesn’t support timeouts. We can work
around this by composing two promises: a url-retrieve promise and
aio-timeout promise. First define a promise-returning function,
aio-select that takes a list of promises and returns (as another
promise) the first promise to resolve:
(defun aio-select (promises)
(let ((result (aio-promise)))
(prog1 result
(dolist (promise promises)
(aio-listen promise (lambda (_)
(aio-resolve
result
(lambda () promise))))))))
We give aio-select both our url-retrieve and timeout promises, and
it tells us which resolved first:
(aio-defun fetch-fortune-4 (url timeout)
(let* ((promises (list (aio-url-retrieve url)
(aio-timeout timeout)))
(fastest (aio-await (aio-select promises)))
(buffer (aio-await fastest)))
(with-current-buffer buffer
(prog1 (buffer-string)
(kill-buffer)))))
Cool! Note: This will not actually cancel the URL request, just move
the async function forward earlier and prevent it from getting the
result.
Threads
Despite aio being entirely about managing concurrent, asynchronous
operations, it has nothing at all to do with threads — as in Emacs 26’s
support for kernel threads. All async functions and promise callbacks
are expected to run only on the main thread. That’s not to say an
async function can’t await on a result from another thread. It just must
be done very carefully.
Processes
The package also includes two functions for realizing promises on
processes, whether they be subprocesses or network sockets.
aio-process-filteraio-process-sentinel
For example, this function loops over each chunk of output (typically
4kB) from the process, as delivered to a filter function:
(aio-defun process-chunks (process)
(cl-loop for chunk = (aio-await (aio-process-filter process))
while chunk
do (... process chunk ...)))
Exercise for the reader: Write an awaitable function that returns a line
at at time rather than a chunk at a time. You can build it on top of
aio-process-filter.
I considered wrapping functions like start-process so that their aio
versions would return a promise representing some kind of result from
the process. However there are so many different ways to create and
configure processes that I would have ended up duplicating all the
process functions. Focusing on the filter and sentinel, and letting the
caller create and configure the process is much cleaner.
Unfortunately Emacs has no asynchronous API for writing output to a
process. Both process-send-string and process-send-region will block
if the pipe or socket is full. There is no callback, so you cannot await
on writing output. Maybe there’s a way to do it with a dedicated thread?
Another issue is that the process-send-* functions are
preemptible, made necessary because they block. The
aio-process-* functions leave a gap (i.e. between filter awaits)
where no filter or sentinel function is attached. It’s a consequence
of promises being single-fire. The gap is harmless so long as the
async function doesn’t await something else or get preempted. This
needs some more thought.
Update: These process functions no longer exist and have been
replaced by a small framework for building chains of promises. See
aio-make-callback.
Testing aio
The test suite for aio is a bit unusual. Emacs’ built-in test suite,
ERT, doesn’t support asynchronous tests. Furthermore, tests are
generally run in batch mode, where Emacs invokes a single function and
then exits rather than pump an event loop. Batch mode can only handle
asynchronous process I/O, not the async functions of aio. So it’s
not possible to run the tests in batch mode.
Instead I hacked together a really crude callback-based test suite. It
runs in non-batch mode and writes the test results into a buffer
(run with make check). Not ideal, but it works.
One of the tests is a sleep sort (with reasonable tolerances). It’s a
pretty neat demonstration of what you can do with aio:
(aio-defun sleep-sort (values)
(let ((promises (mapcar (lambda (v) (aio-sleep v v)) values)))
(cl-loop while promises
for next = (aio-await (aio-select promises))
do (setf promises (delq next promises))
collect (aio-await next))))
To see it in action (M-x sleep-sort-demo):
(aio-defun sleep-sort-demo ()
(interactive)
(let ((values '(0.1 0.4 1.1 0.2 0.8 0.6)))
(message "%S" (aio-await (sleep-sort values)))))
Async/await is pretty awesome
I’m quite happy with how this all came together. Once I had the
concepts straight — particularly resolving to value functions —
everything made sense and all the parts fit together well, and mostly
by accident. That feels good.
nullprogram.com/blog/2019/03/08/
Python has a feature called function decorators. With a little bit of
syntax, the behavior of a function or class can be modified in useful
ways. Python comes with a few decorators, but most of the useful ones
are found in third-party libraries.
PEP 318 suggests a very simple, but practical decorator called
synchronized, though it doesn’t provide a concrete example. Consider
this function that increments a global counter:
counter = 0
def increment():
global counter
counter = counter + 1
If this function is called from multiple threads, there’s a race
condition — though, at least for CPython, it’s not a data
race thanks to the Global Interpreter Lock (GIL). Incrementing
the counter is not an atomic operation, as illustrated by its byte
code:
0 LOAD_GLOBAL 0 (counter)
3 LOAD_CONST 1 (1)
6 BINARY_ADD
7 STORE_GLOBAL 0 (counter)
10 LOAD_CONST 0 (None)
13 RETURN_VALUE
The variable is loaded, operated upon, and stored. Another thread
could be scheduled between any of these instructions and cause an
undesired result. It’s easy to see that in practice:
from threading import Thread
def worker():
for i in range(200000):
increment()
threads = [Thread(target=worker) for _ in range(8)];
for thread in threads:
thread.start()
for thread in threads:
thread.join()
print(counter)
The increment function is called exactly 1.6 million times, but on my
system I get different results on each run:
$ python3 example.py
1306205
$ python3 example.py
1162418
$ python3 example.py
1076801
I could change the definition of increment() to use synchronization,
but wouldn’t it be nice if I could just tell Python to synchronize this
function? This is where a function decorator shines:
from threading import Lock
def synchronized(f):
lock = Lock()
def wrapper():
with lock:
return f()
return wrapper
The synchronized function is a higher order function that accepts a
function and returns a function — or, more specifically, a callable.
The purpose is to wrap and decorate the function it’s given. In this
case the function is wrapped in a mutual exclusion lock. Note: This
implementation is very simple and only works for functions that accept
no arguments.
To use it, I just add a single line to increment:
@synchronized
def increment():
global counter
counter = counter + 1
With this change my program now always prints 1600000.
Syntactic “sugar”
Everyone is quick to point out that this is just syntactic sugar, and
that you can accomplish this without the @ syntax. For example, the
last definition of increment is equivalent to:
def increment():
...
increment = synchronized(increment)
Decorators can also be parameterized. For example, Python’s
functools module has an lru_cache decorator for memoizing a
function:
@lru_cache(maxsize=32)
def expensive(n):
...
Which is equivalent to this very direct source transformation:
def expensive(n):
...
expensive = lru_cache(maxsize=32)(expensive)
So what comes after the @ isn’t just a name. In fact, it looks
like it can be any kind of expression that evaluates to a function
decorator. Or is it?
Syntactic artificial sweetener
Reality is often disappointing. Let’s try using an “identity” decorator
defined using lambda. This decorator will accomplish nothing, but it
will test if we can decorate a function using a lambda expression.
@lambda f: f
def foo():
pass
But Python complains:
@lambda f: f
^
SyntaxError: invalid syntax
Maybe Python is absolutely literal about the syntax sugar thing, and
it’s more like a kind of macro replacement. Let’s try wrapping it in
parentheses:
@(lambda f: f)
def foo(n):
pass
Nope, same error, but now pointing at the opening parenthesis. Getting
desperate now:
@[synchronized][0]
def foo():
pass
Again, syntax error. What’s going on?
Pattern matching
The problem is that the Python language reference doesn’t parse an
expression after @. It matches a very specific pattern that
just so happens to look like a Python expression. It’s not syntactic
sugar, it’s syntactic artificial sweetener!
ator ::= "@" dotted_name ["(" [argument_list [","]] ")"] NEWLINE
In a way, this puts Python in the ranks of PHP 5 and Matlab: two
languages with completely screwed up grammars that can only parse
specific constructions that the developers had anticipated. For
example, in PHP 5 (fixed in PHP 7):
function foo() {
return function() {
return 0;
};
}
foo()();
That is a syntax error:
PHP Parse error: syntax error, unexpected '(', expecting ',' or ';'
Or in any version of Matlab:
That is a syntax error:
Unbalanced or unexpected parenthesis or bracket
In Python’s defense, this strange, limited syntax is only in a single
place rather than everywhere, but I still wonder why it was defined
that way.
Update: Clément Pit-Claudel pointed out the explanation in the PEP,
which references a 2004 email by Guido van Rossum:
I have a gut feeling about this one. I’m not sure where it comes
from, but I have it. It may be that I want the compiler to be able to
recognize certain decorators.
So while it would be quite easy to change the syntax to @test in the
future, I’d like to stick with the more restricted form unless a real
use case is presented where allowing @test would increase readability.
(@foo().bar() doesn’t count because I don’t expect you’ll ever need
that).